반응형
https://www.acmicpc.net/problem/2211
2211번: 네트워크 복구
첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다
www.acmicpc.net
[ 문제풀이 ]
1. visited 배열을 만들고 visited [ i ] = 987654321로 초기화해 줍니다.
2. node struct를 만들어서 연결된 각각의 컴퓨 번호와 비용을 저장합니다.
3. dijkstra를 이용하여 네트워크를 복구하고, 네트워크가 연결될 때마다 ans에 각각의 컴퓨터 번호를 push 해줍니다.
4. 연결된 네트워크의 개수를 출력하고, 각각의 번호를 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | #include<iostream> #include<queue> #include<vector> using namespace std; int N, M; vector<pair<int, int>> list[1001]; int visited[1001]; vector<pair<int,int>> ans; struct node { int before; int cur; int cost; }; struct cmp { bool operator()(node right, node left) { return left.cost < right.cost; } }; int main() { priority_queue<node, vector<node>, cmp> pq; scanf("%d %d", &N, &M); fill(visited, visited + N + 1, 987654321); visited[1] = 0; for (int i = 0; i < M; i++) { int A, B, C; scanf("%d %d %d", &A, &B, &C); list[A].push_back({ B,C }); list[B].push_back({ A,C }); } pq.push({ 0,1,0 }); while (!pq.empty()) { const int before = pq.top().before; const int cur = pq.top().cur; const int cost = pq.top().cost; pq.pop(); if (visited[cur] < cost) continue; ans.push_back({ before,cur }); for (auto& next : list[cur]) { if (visited[next.first] > cost + next.second) { visited[next.first] = cost + next.second; pq.push({ cur, next.first, cost + next.second }); } } } printf("%d\n", ans.size() - 1); for (int i = 1; i < ans.size(); i++) { printf("%d %d\n", ans[i].first, ans[i].second); } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 11658번 - 구간 합 구하기 3 (C++) (0) | 2023.02.08 |
|---|---|
| [ 백준 ] 2458번 - 키 순서 (C++) (0) | 2023.02.07 |
| [ 백준 ] 17835번 - 면접보는 승범이네 (C++) (0) | 2023.02.05 |
| [ 백준 ] 1368번 - 물대기 (C++) (0) | 2023.02.04 |
| [ 백준 ] 1261번 - 알고스팟 (C++) (0) | 2023.02.03 |