/* Bellman - Ford */#include#include #include #define Inf 0x7fffffff#define MaxV 10000#define MaxE 10000using namespace std;int N,M;struct Edge{ int to,next,w;}edge[MaxE];int size,head[MaxV];void InsertEdge(int from,int to,int w){ edge[size].to=to; edge[size].w = w; edge[size].next=head[from]; head[from]=size++;}int dist[MaxV];bool bellmanFord(int s){ int i,j,k; int to; for(i=1;i<=N;i++) dist[i]=Inf; dist[s]=0; for(i=1;i<=N-1;i++) //每个点都更新N-1 次 { for(j=1;j<=N;j++) //每个点更新一次 { if(dist[j]==Inf) continue; //如果不能到达，则下一个点 for(k=head[j];k+1;k=edge[k].next) { to=edge[k].to; if(edge[k].w!=Inf&&dist[to]>dist[j]+edge[k].w) dist[to]=dist[j]+edge[k].w; } } } for(j=1;j<=N;j++) { if(dist[j]==Inf) continue; //如果不能到达这个点 for(k=head[j];k+1;k=edge[k].next) { to=edge[k].to; if(edge[k].w!=Inf&&dist[to]>dist[j]+edge[k].w) return false; } } return true;}void init(){ int from,to,w; scanf("%d%d",&N,&M); size=0; memset(head,-1,sizeof(head)); for(int i=0;i