RT

这是我的评测记录（用的bellman-ford）

很奇怪，下载了数据和输出

5 15 5
2 2 270
1 4 89
2 1 3
5 5 261
5 2 163
5 5 275
4 5 108
4 4 231
3 4 213
3 3 119
3 1 77
3 1 6
2 4 83
5 5 196
5 5 94
//分割线
166 163 2147483647 246 0 

这是我的程序和输出

//Think twice,code once
#define ll long long
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int N=1e4+10,M=5e5+10;
const int Inf=1061109567;
struct node{
    int u,v,w;
    node(int u0=0,int v0=0,int w0=0){
        u=u0; v=v0; w=w0;
    }
}e[M];
int n,m,s;
int d[N];
inline int read(){//
    int xx=0,ff=1; char cc=getchar();//
    while(!isdigit(cc)){if(cc=='-') ff=-1; cc=getchar();}
    while(isdigit(cc)){xx=xx*10+cc-'0'; cc=getchar();}
    return xx*ff;
}
inline bool can(int id){return d[e[id].u]==Inf?false:d[e[id].u]+e[id].w<d[e[id].v];}
int main(){
    n=read(); m=read(); s=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read(),w=read();
        e[i]=node(u,v,w);
    }
    //bellman-ford
    memset(d,0x3f,sizeof(d)); d[s]=0;
    for(int i=1;i<n;++i){//V
        bool flag=true;
        for(int j=1;j<=m;++j)//E
            if(can(j))//relax
                d[e[j].v]=d[e[j].u]+e[j].w,flag=false;  
        if(flag) break;
    }
    for(int i=1;i<=n;++i)
        if(d[i]!=Inf) printf("%d ",d[i]);
        else printf("2147483647 ");
    return 0;
}
//分割线
166 163 2147483647 246 0 

一 模 一 样

耐 人 寻 味