문제링크 : https://www.acmicpc.net/problem/1922
문제설명
이 문제는 1197 스패닝 트리 문제와 똑같이 최소 스패닝 트리만 구하면 되는 문제이다.
이번 역시 프림 알고리즘으로 풀었으며, 풀이는 1197 스패닝트리 포스팅와 같으니 생략하겠다.
소스코드
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 | #include <iostream> #include <vector> #include <queue> using namespace std; int n, m, sum; vector<pair<int,int> >v[1001]; // 입력 받을 그래프 priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq; int visited[1001]; void prim(int node) { visited[node] = true; for (int i = 0; i < v[node].size(); i++) { if (!visited[v[node][i].second]) { pq.push(make_pair(v[node][i].first,v[node][i].second)); } } while(!pq.empty()) { int cost = pq.top().first; int nextnode = pq.top().second; pq.pop(); if (!visited[nextnode]) { sum += cost; prim(nextnode); } } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for (int i = 0; i < m; i++) { int a1, a2, a3; cin >> a1 >> a2 >> a3; v[a1].push_back(make_pair(a3,a2)); v[a2].push_back(make_pair(a3,a1)); } prim(1); cout << sum; return 0; } | cs |
