//Author: Bishal Sarang //Floyd Implementation /* Sample Input 4 5 1 2 5 1 4 24 2 4 6 3 4 4 3 2 7 3 1 2 3 1 1 4 */ /*Sample Output 5 -1 11 */ #include #define inf 10000000 using namespace std; typedef long long ll; ll dist[405][405]; void floyd(int V) { for(int k = 1; k <= V; k++) for(int i = 1; i <= V; i++) for(int j = 1; j <= V; j++) { //Update if(dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]; } } int main() { int n, m; //Number of vertex and edges cin >> n >> m; int adj[n + 3][n + 3]; //Fill distance table such that distance to self node is 0 and all other is infinity for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) { if(i == j) //Distance to self node is 0 { adj[i][j] = 0; dist[i][j] = 0; } else { adj[i][j] = inf; dist[i][j] = inf; } } int u, v, w; //Input Directed Edge (u, v) with weight w for(int i = 0; i < m; i++) { cin >> u >> v >> w; adj[u][v] = w; dist[u][v] = w; } int q; cin >> q; //Call Floyd Procedure floyd(n); //Get distance from u to v from distance table while(q--) { cin >> u >> v; //If no path is available if(dist[u][v] == inf) cout << -1 <<"\n"; //Display the distance else cout << dist[u][v] << "\n"; } return 0; }

Floyd Shortest path