Bellman-Fordアルゴリズムc++実装(前向き星)
1695 ワード
/* Bellman - Ford */
#include <iostream>
#include <cstdio>
#include <cstring>
#define Inf 0x7fffffff
#define MaxV 10000
#define MaxE 10000
using 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<M;i++)
{
scanf("%d%d%d",&from,&to,&w);
InsertEdge(from,to,w);
}
}
int main()
{
freopen("in.txt","r",stdin);
init();
if(bellmanFord(1)) printf("OK");
else printf("No");
return 0;
}