社区讨论

请问我的弗洛伊德是什么错?

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 条回复,欢迎继续交流。

正在加载回复...