Advertisement
tepyotin2

Road Reparation

Jun 1st, 2025
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. struct Repair{
  8.     ll node, weight;
  9.     bool operator>(const Repair &a) const{
  10.         return weight>a.weight;
  11.     }
  12. };
  13.  
  14. ll n, m;
  15. vector<vector<Repair>> rep;
  16. priority_queue<Repair, vector<Repair>, greater<Repair>> pq;
  17. vector<bool> visited;
  18. vector<int> dist;
  19. ll ans = 0;
  20.  
  21. int main(){
  22.     //freopen("roadrepair.in", "r", stdin);
  23.    
  24.     cin >> n >> m;
  25.     rep.resize(n+1);
  26.     for(ll i=0; i<m; i++){
  27.         ll a, b, c;
  28.         cin >> a >> b >> c;
  29.         rep[a].push_back({b, c});
  30.         rep[b].push_back({a, c});
  31.     }
  32.     visited.resize(n+1);
  33.     dist.resize(n+1, INT_MAX);
  34.     dist[1] = 0;
  35.     pq.push({1, 0});
  36.     while(!pq.empty()){
  37.         Repair cur = pq.top();
  38.         pq.pop();
  39.         if(visited[cur.node]) continue;
  40.         visited[cur.node] = true;
  41.         ans+=dist[cur.node];
  42.         for(Repair next: rep[cur.node]){
  43.             if(!visited[next.node] && next.weight<dist[next.node]){
  44.                 dist[next.node] = next.weight;
  45.                 pq.push({next.node, dist[next.node]});
  46.             }
  47.         }
  48.     }
  49.     for(ll i=1; i<=n; i++){
  50.         if(!visited[i]){
  51.             cout << "IMPOSSIBLE" << '\n';
  52.             return 0;
  53.         }
  54.     }
  55.     cout << ans << '\n';
  56.    
  57.     return 0;
  58. }
  59.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement