图论学习 Floyd求最短路
作者:
travel2.0
,
2024-01-27 07:57:12
,
所有人可见
,
阅读 59
Floyd求最短路
算法分析:
1.运用了dp思想;dp[k,i,j] 表示从i点到j点经过了k个点的距离
2.状态转移方程:dp[k,i,j] = dp[k-1,i,k] + dp[k-1,k,j];
即为从i到k经过了k-1个点,从k到j经过了k-1个点的距离之和;
3.初始化的时候要注意,自环为0,其他无穷大;
4.输出判断还是 INF / 2;
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
const int N = 210,INF = 1e9;
int g[N][N];
void floyd(){
for(int k = 1; k <= n;k++){
for(int j = 1;j <= n;j++){
for(int i = 1; i <= n;i++){
g[j][i] = min(g[j][i],g[j][k]+g[k][i]);
}
}
}
}
int main(){
cin>>n>>m>>q;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(i == j) g[i][j] = 0;
else g[i][j] = INF;
}
}
while(m--){
int a,b,c; cin>>a>>b>>c;
g[a][b] = min(g[a][b],c);
}
floyd();
while(q--){
int l,r; cin>>l>>r;
if(g[l][r] > INF / 2) puts("impossible");
else cout<<g[l][r]<<endl;
}
return 0;
}