SHARE
TWEET

Untitled

a guest Feb 17th, 2019 114 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. ifstream fin("dijkstra.in");
  5. ofstream fout("dijkstra.out");
  6.  
  7. long long n, v, D[101], T[101], A[101][101], c, x, i, j;
  8. bool S[101];
  9. int main()
  10. {
  11.     fin>>n>>v;
  12.     for( i=1; i<=n; i++)
  13.         for( j=1; j<=n; j++)
  14.  
  15.             if(i!=j)
  16.                 A[i][j]=INT_MAX;
  17.     while(fin>>i>>j>>c)
  18.         A[i][j]=c;
  19.     for( i=1; i<=n; i++)
  20.     {
  21.         D[i]=A[v][i];
  22.         if(D[i]!=INT_MAX)
  23.             T[i]=v;
  24.     }
  25.     S[v]=1;
  26.     for( i=1; i<n; i++)
  27.     {
  28.         int minim=INT_MAX;
  29.         for(j=1; j<=n; j++)
  30.             if(S[j]==0 && D[j]<minim)
  31.             {
  32.                 minim=D[j];
  33.                 x=j;
  34.             }
  35.         for(j=1; j<=n; j++)
  36.         {
  37.             if(S[j]==0 && D[j]>D[x]+A[x][j])
  38.             {
  39.                 D[j]=D[x]+A[x][j];
  40.                 T[j]=x;
  41.             }
  42.         }
  43.         S[x]=1;
  44.     }
  45.     for(i=1; i<=n; i++)
  46.         if(D[i]<INT_MAX)
  47.             fout<<D[i] << " ";
  48.         else
  49.             fout<< "-1";
  50.     return 0;
  51. }
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