Bellman-Ford打这题,#1没过?!

看这题O(NM)复杂度能过就打了Bellman为什么90分,第一个点有什么陷阱吗?

4 条评论

  • @ 2016-10-15 23:38:12

    膜膜膜

  • @ 2016-10-15 20:27:40

    膜膜膜

  • @ 2016-10-15 20:18:56

    膜膜膜

  • @ 2016-10-15 20:01:51

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<algorithm>
    #include<math.h>
    using namespace std;
    long long dis[1010];
    struct node{
    int u,v;
    long long w;
    }e[100100];
    int main(){
    long long INF=(long long)pow(10,18);
    int n,m,s,i;
    scanf("%d%d%d",&n,&m,&s);
    for(i=1;i<=m;i++)
    scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w);
    for(i=1;i<=n;i++)dis[i]=INF;
    dis[s]=0;
    int k;
    for(k=1;k<n;k++)
    for(i=1;i<=m;i++)
    if(dis[e[i].v]>dis[e[i].u]+e[i].w)
    dis[e[i].v]=dis[e[i].u]+e[i].w;
    int flag=0;
    for(i=1;i<=m;i++)
    if(dis[e[i].v]>dis[e[i].u]+e[i].w){
    flag=1;
    break;
    }
    if(flag==1)puts("-1");
    else for(i=1;i<=n;i++){
    if(dis[i]==INF)puts("NoPath");
    else printf("%lld\n",dis[i]);
    }
    }
    代码放在这里

  • 1

信息

ID
1053
难度
8
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
7499
已通过
674
通过率
9%
被复制
9
上传者