45 lines
949 B
C++
45 lines
949 B
C++
// lanqiao 1121 蓝桥公园(floyd)
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
#define int long long
|
|
const int N = 4e2+10;
|
|
int d[N][N];
|
|
int inf = 2e18;
|
|
signed main(){
|
|
// 请在此输入您的代码
|
|
ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
|
|
int n, m, q; cin >> n >> m >> q;
|
|
for(int i = 1; i <= n; i++){
|
|
for(int j = 1; j <= n; j++){
|
|
d[i][j] = inf; // 全部初始化为最大值
|
|
}
|
|
d[i][i] = 0; // 到自己的距离为0
|
|
}
|
|
while(m--){
|
|
int u, v, w; cin >> u >> v >> w;
|
|
d[u][v] = min(d[u][v], w);
|
|
d[v][u] = min(d[v][u], w);
|
|
}
|
|
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]));
|
|
}
|
|
}
|
|
}
|
|
for(int i = 1; i <= q; i++){
|
|
int st, ed; cin >> st >> ed;
|
|
cout << ((d[st][ed] >= inf)?-1:d[st][ed]) << '\n';
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
/* test samples -> 1 3 2
|
|
3 3 3
|
|
1 2 1
|
|
1 3 5
|
|
2 3 2
|
|
1 2
|
|
1 3
|
|
2 3
|
|
*/ |