Floyd (基于动态规划)
dist[i][j]
表示从i到j最多经过k点的最小距离。
分为两种情况:经过k和不经过k:
不经过k则为dist[i][j] = dist[i][j]
。
经过k则为dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
。
由于k时逐渐增大所以dist[i][k]和dist[k][j]的最小距离之前已经得出。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 210, INF = 0x3f3f3f3f;
int n, m, k;
int dist[N][N];
int main()
{
cin >> n >> m >> k;
memset(dist, 0x3f, sizeof dist);
for (int i = 1; i <= n; i ++ ) dist[i][i] = 0;
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
dist[a][b] = min(dist[a][b], c);
}
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
while (k -- )
{
int a, b;
cin >> a >> b;
if (dist[a][b] >= INF / 2) puts("impossible");
else cout << dist[a][b] << endl;
}
return 0;
}