득이공간

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net #include #include #include #include #include #include using namespace std; const int& Infinite = INT_MAX; vector Neighbors; priority_queue SearchQueue; vector Solution; vector Dijkstra(int N, int Start) { vector Times; Times.reserve(N); for (i..

1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net #include #include #include #include using namespace std; void Play() { int N, K; cin >> N >> K; vector Times; Times.reserve(N); vector EndTimes; Times.reserve(N); vector Neighbors; Neighbors.reserve(N); vector Entries; Entries.reserve(N); for (int i = 0; i ..

2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net #include #include #include #include using namespace std; vector Neighbors; vector Entries; vector Sequence; queue SearchQueue; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; cin >> N >> M; Neighbors.r..

1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net #include #include using namespace std; vector RootNode; vector Schedule; int Find(int Node) { if (Node == RootNode[Node]) { return Node; } return RootNode[Node] = Find(RootNode[Node]); } void Union(int NodeA, int NodeB) { int RootNodeA = Find(NodeA); int RootN..

1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net #include #include using namespace std; vector RootNode; int Find(int Node) { if (Node == RootNode[Node]) { return Node; } return RootNode[Node] = Find(RootNode[Node]); } void Union(int NodeA, int NodeB) { int RootNodeA = Find(NodeA); int R..

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net #include #include #include #include using namespace std; const int& MaxSize = 100001; const int& Infinite = INT_MAX; priority_queue SearchQueue; int Times[MaxSize]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); in..

1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net #include #include #include #include using namespace std; const int& Infinite = INT_MAX; vector Neighbors; vector LinkState; priority_queue SearchQueue; void Init(int InN, int InM) { Neighbors.reserve(InN); for (int i = 0; i < InN; ++i) { Nei..

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net #include #include #include #include using namespace std; vector Neighbors; vector LinkState; priority_queue NonVisited; // 오름차순 PQ const int& Infinite = INT_MAX; void Init(int InV, int InE, int InK) { ios::sync_with_stdio(false); cin.tie(N..

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net #include #include #include using namespace std; vector Schedule; vector Solution; vector Solutions; void DFS(int N, int Current, int Working, vector Solution) { if (Working > 0) { --Working; } if (Current == N - 1) { if (Working == 0 && Schedule[Current].first N; Schedule.reserve(N); for (int i = 0; i > T >> P;..

1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net #include #include #include using namespace std; vector Lines; int main() { int K, N; cin >> K >> N; Lines.reserve(K); for (int i = 0; i > Line; Lines.emplace_back(Line); } int Result = 0; long long Length = 0; long lo..