Advertisement
aimon1337

Untitled

Apr 19th, 2021
908
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.86 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. ifstream fin("bac.txt");
  4. ofstream fout("k.out");
  5. const int inf=1<<20;
  6. int n,m,A[100][100],P[100];
  7.  
  8. void citire()
  9. {    int i,j,k,c;
  10.      fin>>n>>m;
  11.      for(i=1;i<n;i++)
  12.         for(j=i+1;j<=n;j++)
  13.             A[i][j]=A[j][i]=inf;
  14.      for(int k=1;k<=m;k++)
  15.         { fin>>i>>j>>c;
  16.           A[i][j]=A[j][i]=c;
  17.         }
  18. }
  19.  
  20. int main()
  21. {
  22.     int i,k,minn,x;
  23.     int s=0;
  24.     citire();
  25.     for(i=2;i<=n;i++) P[i]=1;
  26.     for(k=1;k<n;k++)
  27.     {
  28.        minn=inf;
  29.        for(i=1;i<=n;i++)
  30.            if(P[i] && A[P[i]][i]<minn)
  31.            {
  32.                minn=A[P[i]][i]; x=i;
  33.            }
  34.         s+=A[P[x]][x];
  35.        for(i=1;i<=n;i++)
  36.            if(P[i] && A[P[i]][i]>A[i][x])
  37.                 P[i]=x;
  38.        P[x]=0;
  39.     }
  40.     cout<<s<<" ";
  41.     fin.close();
  42.     fout.close();
  43.     return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement