如有错误请指正!
图
状态转移方程
dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 210;
int dist[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 ++){
dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
}
}
}
}
int main(){
cin >> n >> m >> q;
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);
}
floyd();
while(q --){
int x,y;
cin >> x >> y;
if(dist[x][y] >= 0x3f3f3f3f/2) printf("impossible\n"); //为什么是>=03xf3f3f3f/2?因为存在负权边 所以0x3f3f3f3f这个值可能会因为负值被更新 但值依然远大于0x3f3f3f3f/2
else printf("%d\n",dist[x][y]);
}
return 0;
}
卡钩晚上直播白天搁这打程序是吧,有没有可能给重生修bug呢
卡神写写代码不过分吧
易大山
账号已注销我想账号已注销了
我一直都是锁住啊/(ㄒoㄒ)/~~
妙啊
为什么dist[i][i] = 0呢?自环的权重不是不一定是0吗?
因为求最短路径
我理解错了,我以为自己到自己得有路径,忘记其实是0了
大佬借个图
简单明了,下次一定三连
老哥牛啊,深得y总真传,hh
图已存