daily pastebin goal
53%
SHARE
TWEET

Untitled

a guest Jan 10th, 2015 199 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. long long dist[250][250];
  6.  
  7. int main()
  8. {
  9.         int C, F;
  10.         cin >> C >> F;
  11.  
  12.         for(int i = 1; i <= C; i++)
  13.         {
  14.                 for(int j = 1; j <= C; j++)
  15.                 {
  16.                         dist[i][j] = 1000000000000000LL; //set all to infinity initially
  17.                 }
  18.                 dist[i][i] = 0; //distance to self is zero
  19.         }
  20.  
  21.         for(int i = 0; i < F; i++)
  22.         {
  23.                 int u, v, p;
  24.                 cin >> u >> v >> p;
  25.                 dist[u][v] = dist[v][u] = p;
  26.                 //if an edge exists between u,v then initial dist between them
  27.                 //is set to the weight of the edge
  28.         }
  29.  
  30.         //Floyd-Warshall Algorithm
  31.         for(int k = 1; k <= C; k++)
  32.         {
  33.                 for(int i = 1; i <= C; i++)
  34.                 {
  35.                         for(int j = 1; j <= C; j++)
  36.                         {
  37.                                 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  38.                         }
  39.                 }
  40.         }
  41.  
  42.         long long int ans = 0;
  43.         for(int i = 1; i <= C; i++)
  44.         {
  45.                 for(int j = 1; j <= C; j++)
  46.                 {
  47.                         if(dist[i][j] != 1000000000000000LL) ans = max(ans, dist[i][j]);
  48.                         //finding maximum of all non-infinity distances
  49.                 }
  50.         }
  51.  
  52.         cout << ans;
  53. }
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