#include <bits/stdc++.h> using namespace std; const int N = 210, INF = 0x3f3f3f3f; int d[N][N], n, m, q; 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 >> 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; for (int i = 1; i <= m; i ++ ){ int u, v, w; cin >> u >> v >> w; d[u][v] = min(d[u][v], w); } Floyd(); while (q--){ int u, v; cin >> u >> v; if (d[u][v] >= INF / 2) cout << "impossible\n"; else cout << d[u][v] << "\n"; } return 0; }
acwing 模板:https://www.acwing.com/problem/content/856/