AcWing 854. Floyd求最短路
原题链接
简单
作者:
C___
,
2021-12-05 21:20:26
,
所有人可见
,
阅读 167
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N = 2 * 1e2 + 10, INF = 0x3f3f3f3f;
int n, m, k, dist[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++){
// i -> j 的最短路 / i -> k 的最短路 / j -> k 的最短路
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
int main(void){
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist[i][j] = INF;
// 自己到自己路径为 0
if(i == j) dist[i][j] = 0;
}
}
for(int i = 1; i <= m; i++) {
int a, b, c; scanf("%d%d%d", &a, &b, &c);
// 取 a -> b 之间的最短路
dist[a][b] = min(dist[a][b], c);
}
Floyd();
for(int i = 1; i <= k; i++){
int a, b; scanf("%d%d", &a, &b);
// 如果数量级与 INF 为同一数量级则表明到达不了
if(dist[a][b] > INF>>1) printf("impossible\n");
else printf("%d\n", dist[a][b]);
}
return 0;
}