Advertisement
mickypinata

USACO-T040: Agri-net

Dec 17th, 2021
917
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: agrinet
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. const int N = 100 + 5;
  11.  
  12. int mat[N][N], dist[N], idx[N];
  13.  
  14. int main(){
  15.     freopen("agrinet.in", "r", stdin);
  16.     freopen("agrinet.out", "w", stdout);
  17.  
  18.     int nVertex;
  19.     scanf("%d", &nVertex);
  20.     dist[0] = 1e9;
  21.     for(int u = 1; u <= nVertex; ++u){
  22.         for(int v = 1; v <= nVertex; ++v){
  23.             scanf("%d", &mat[u][v]);
  24.         }
  25.         dist[u] = 1e9;
  26.         idx[u] = u;
  27.     }
  28.     int mst = 0;
  29.     dist[1] = 0;
  30.     for(int i = 0; i < nVertex; ++i){
  31.         int u = 0;
  32.         for(int j = 1; j <= nVertex - i; ++j){
  33.             if(dist[j] < dist[u]){
  34.                 u = j;
  35.             }
  36.         }
  37.         mst += dist[u];
  38.         for(int v = 1; v <= nVertex - i; ++v){
  39.             dist[v] = min(dist[v], mat[idx[u]][idx[v]]);
  40.         }
  41.         swap(idx[u], idx[nVertex - i]);
  42.         swap(dist[u], dist[nVertex - i]);
  43.     }
  44.     cout << mst << '\n';
  45.  
  46.     fclose(stdin);
  47.     fclose(stdout);
  48.     return 0;
  49. }
  50.  
Advertisement
RAW Paste Data Copied
Advertisement