题目描述
用邻接矩阵 d[i, j] 存储所有的边
三种循环
for(k = 1; k <= n; k )
for(i = 1; i <= n; i )
for(j = 1; j <= n; j ++)
d[i, j] = min(d[i, j], d[i, k] + d[k, j])
结束之后,d[i, j] 存的就是 i 到 j 的最短路的长度
基于动态规划
样例
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210, INF = 1e9;
int n, m, Q;
int d[N][N];
void floyd()
{
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main()
{
scanf("%d%d%d", &n, &m, &Q);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(i == j) d[i][j] = 0;
else d[i][j] = INF;
while(m --)
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
d[a][b] = min(d[a][b], w);
}
floyd();
while(Q--)
{
int a, b;
scanf("%d%d", &a, &b);
// if里面的判断用 d[a][b] == INF 通过不了,
// 因为 a 和 b 之间没有通路的话,它们的距离不一定是正无穷,可能比 正无穷小一些
if(d[a][b] > INF / 2) puts("impossible");
else printf("%d\n", d[a][b]);
}
return 0;
}