题目描述
blablabla
样例
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 210, INF = 1e9;
int d[N][N];
int 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 = 0; i<m; i++){
int a, b, c;
cin >> a >> b >> c;
d[a][b] = min(d[a][b], c);
}
floyd();
while(q--){
int x, y;
cin >> x >> y;
if(d[x][y] > INF/2) puts("impossible");
else cout << d[x][y] << endl;
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla