Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- struct Repair{
- ll node, weight;
- bool operator>(const Repair &a) const{
- return weight>a.weight;
- }
- };
- ll n, m;
- vector<vector<Repair>> rep;
- priority_queue<Repair, vector<Repair>, greater<Repair>> pq;
- vector<bool> visited;
- vector<int> dist;
- ll ans = 0;
- int main(){
- //freopen("roadrepair.in", "r", stdin);
- cin >> n >> m;
- rep.resize(n+1);
- for(ll i=0; i<m; i++){
- ll a, b, c;
- cin >> a >> b >> c;
- rep[a].push_back({b, c});
- rep[b].push_back({a, c});
- }
- visited.resize(n+1);
- dist.resize(n+1, INT_MAX);
- dist[1] = 0;
- pq.push({1, 0});
- while(!pq.empty()){
- Repair cur = pq.top();
- pq.pop();
- if(visited[cur.node]) continue;
- visited[cur.node] = true;
- ans+=dist[cur.node];
- for(Repair next: rep[cur.node]){
- if(!visited[next.node] && next.weight<dist[next.node]){
- dist[next.node] = next.weight;
- pq.push({next.node, dist[next.node]});
- }
- }
- }
- for(ll i=1; i<=n; i++){
- if(!visited[i]){
- cout << "IMPOSSIBLE" << '\n';
- return 0;
- }
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
