#include <stdio.h> #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <map> using namespace std; int V, E; vector<pair<int, int>> v[10010]; int visited[10010]; int cost; void prim() { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; visited[1] = 1; for(int i = 0; i < v[1].size(); i++) { pq.push({v[1][i].second, v[1][i].first}); } while(!pq.empty()) { int now = pq.top().second; int nowCost = pq.top().first; pq.pop(); if(visited[now] == 0) { visited[now] = 1; cost += nowCost; } else { continue; } for(int i = 0; i < v[now].size(); i++) { int next = v[now][i].first; int nextCost = v[now][i].second; if(visited[next] == 0) { pq.push({nextCost, next}); } } } } int main(void) { // freopen("B1197_input.txt", "r", stdin); cin >> V >> E; for(int i = 1; i <= E; i++) { int from, to, weight; cin >> from >> to >> weight; // 양방향 삽입 v[from].push_back({to, weight}); v[to].push_back({from, weight}); } prim(); cout << cost << endl; return 0; } | cs |
'Baekjoon > MST' 카테고리의 다른 글
[백준 1774] 우주선과의 교감 (Prim) (C/C++) (★★) (0) | 2020.05.18 |
---|