Floyd求最短路(多源最短路)
#include<bits/stdc++.h>
using namespace std;
const int N = 210, M = 2e+10, INF = 1e9;
int n , m , x , k , y ,z;
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()
{
cin >> n >> m >> k;
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 -- )
{
cin >> x >> y >> z;
d[x][y] = min(d[x][y] , z);
//注意保存最小边
}
floyd();
while(k--)
{
cin >> x >> y;
if(d[x][y] > INF) puts("impossible");
//由于有负权边存在所以约大过INF/2也很合理
else cout << d[x][y] << endl;
}
return 0;
}