Floyd算法

基于动态规划：

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数n，m，k

接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。

输出格式

共k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。

数据范围

输入样例：

输出样例：

impossible
1


#################################################################

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 210, INF = 1e9;
 5 int n, m, q;
 6 int d[N][N];
 7 //基于动态规划思路
 8 void floyd(){
 9     for(int k = 1;k <= n;++k)
10         for(int i = 1;i <= n;++i)
11             for(int j = 1;j <= n;++j)
12                 d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
13 }
14 
15 int main(){
16     cin >> n >> m >> q;
17     //init d数组
18     for(int i = 1;i <= n;++i)
19         for(int j = 1;j <= n;++j)
20             if(i == j) d[i][j] = 0;
21             else d[i][j] = INF;
22     
23     while(m--){
24         int a, b, c;
25         cin >> a >> b >> c;
26         d[a][b] = min(d[a][b], c);
27     }
28     floyd();
29     while(q--){
30         int x, y;
31         cin >> x >> y;
32         if(d[x][y] >= INF >> 1)cout << "impossible" << endl;
33         else cout << d[x][y] << endl;
34     }
35     return 0;
36 }

View Code

end