• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Jan 10th, 2015 204 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;
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.

Top