Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- long long dist[250][250];
- int main()
- {
- int C, F;
- cin >> C >> F;
- for(int i = 1; i <= C; i++)
- {
- for(int j = 1; j <= C; j++)
- {
- dist[i][j] = 1000000000000000LL; //set all to infinity initially
- }
- dist[i][i] = 0; //distance to self is zero
- }
- for(int i = 0; i < F; i++)
- {
- int u, v, p;
- cin >> u >> v >> p;
- dist[u][v] = dist[v][u] = p;
- //if an edge exists between u,v then initial dist between them
- //is set to the weight of the edge
- }
- //Floyd-Warshall Algorithm
- for(int k = 1; k <= C; k++)
- {
- for(int i = 1; i <= C; i++)
- {
- for(int j = 1; j <= C; j++)
- {
- dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
- }
- }
- }
- long long int ans = 0;
- for(int i = 1; i <= C; i++)
- {
- for(int j = 1; j <= C; j++)
- {
- if(dist[i][j] != 1000000000000000LL) ans = max(ans, dist[i][j]);
- //finding maximum of all non-infinity distances
- }
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement