SHARE
TWEET

Untitled

a guest Feb 18th, 2020 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<fstream>
  2. using namespace std;
  3. ifstream f("prim.in");
  4. ofstream g("prim.out");
  5. const int inf=1000000000;
  6. int n,m,a[101][101],viz[101],d[101],t[101];
  7. int main()
  8. {
  9.     f>>n>>m;
  10.     for(int i=1;i<=n;i++)
  11.         for(int j=1;j<=n;j++)
  12.         if(i!=j) a[i][j]=inf;
  13.     for(int p,q,cost,i=1;i<=m;i++)
  14.     {
  15.         f>>p>>q>>cost;
  16.         a[p][q]=a[q][p]=cost;
  17.     }
  18.     for(int j=1;j<=n;j++)
  19.     {
  20.         d[j]=a[1][j];
  21.         if(j!=1) t[j]=1;
  22.     }
  23.     viz[1]=1;d[0]=inf;
  24.     for(int k=2;k<=n;k++)
  25.     {
  26.         int poz=0;
  27.         for(int i=1;i<=n;i++)
  28.             if(!viz[i]&&d[i]<d[poz]) poz=i;
  29.         viz[poz]=1;
  30.         for(int i=1;i<=n;i++)
  31.             if(!viz[i]&&d[i]>a[poz][i])
  32.             {
  33.                 d[i]=a[poz][i];
  34.                 t[i]=poz;
  35.             }
  36.     }
  37.     int cost=0;
  38.     for(int i=1;i<=n;i++)
  39.         cost+=d[i];
  40.     g<<cost<<'\n';
  41.     for(int i=1;i<=n;i++)
  42.         g<<t[i]<<' ';
  43.     g.close();f.close();
  44.     return 0;
  45. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top