社区讨论

Floyd0分求助

P1078[NOIP 2012 普及组] 文化之旅(疑似错题)参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lo7sif55
此快照首次捕获于
2023/10/27 07:02
2 年前
此快照最后确认于
2023/10/27 07:02
2 年前
查看原帖
似乎只有一个点的输出不是-1
CPP
#include<bits/stdc++.h>
using namespace std;
int floyd[110][110],cont[110],fuck[110][110];
int n,k,m,s,t,u,v,d;
int main(){
    scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            floyd[i][j]=2147483646;
    for(int i=1;i<=n;++i)
        scanf("%d",&cont[i]);
    for(int i=1;i<=k;++i)
        for(int j=1;j<=k;++j)
            scanf("%d",&fuck[i][j]);
    for(int i=1;i<=m;++i) {
        scanf("%d%d%d",&u,&v,&d);
        if(d<floyd[u][v]){
            if(fuck[cont[u]][cont[v]]==0)floyd[u][v]=d;
            if(fuck[cont[v]][cont[u]]==0)floyd[v][u]=d;
        }
    }  
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)  
            for(int j=1;j<=n;j++)
                floyd[i][j]=min(floyd[i][j],floyd[i][k]+floyd[k][j]);
    if(floyd[s][t]==2147483646)
        printf("-1");
    else    
        printf("%d",floyd[s][t]);            
    return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...