AcWing 854. Floyd求最短路
原题链接
简单
作者:
依普昔侬
,
2020-03-28 22:51:00
,
所有人可见
,
阅读 735
基于动态规划,k是中间结点,遍历所有可能,更新i,j的距离;
#include<iostream>
#include<cstring>
using namespace std;
const int N = 230;
int d[N][N];
int n, m, k;
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()
{
cin>> n >> m >> k;
memset(d, 0x3f, sizeof d); //初始化所有点都不通
for(int i = 1; i <= n; i++) d[i][i] = 0; //初始化自己到自己;如果设成INF,那么最后求出
int x, y, z; //的d[i][i]表示从i出发再回到i的最短距离,
for(int i = 0; i < m; i++) //但在这道题目里在查询的时候应该返回0。(引用yxc)
{
scanf("%d%d%d", &x, &y, &z);
d[x][y] = min(d[x][y], z);
}
floyd();
for(int i = 0; i < k; i++)
{
scanf("%d%d", &x, &y);
if(d[x][y] > 0x3f3f3f3f/2) cout<< "impossible" << endl; //因为存在负边;
else cout<< d[x][y] << endl;
}
return 0;
}