社区讨论
请问我的弗洛伊德是什么错?
P3371【模板】单源最短路径(弱化版)参与者 6已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mi5i3xmf
- 此快照首次捕获于
- 2025/11/19 12:27 4 个月前
- 此快照最后确认于
- 2025/11/19 12:27 4 个月前
CPP
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF=100010;
int dp[10001][10001];
int main(){
int n,m,s;
scanf("%d%d%d",&n,&m,&s);
int x,y;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i==j)dp[i][j]=0;
else dp[i][j]=INF;
}
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
scanf("%d",dp[x]+y);
}
//for(int i=1;i<=n;i++)
// for(int j=1;j<=n;j++)
// cout<<dp[i][j]<<" ";
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
for(int i=1;i<=n;i++){
if(dp[s][i]==INF)printf("2147483647 ");
else printf("%d ",dp[s]+i);
}
cin>>x;
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...