Is the Information Reliable?(差分约束)

#include <stdio.h>
const int INF = 99999999 ;
int cnt,m ,n ,dist[15010] ;
structnode
{
    int u,v,w ;
}edge[10700700] ;
void addedge(int u,int v,int w)
{
    edge[cnt].u = u ;
    edge[cnt].v = v ;
    edge[cnt].w = w ;
    cnt++ ;
}
bool bellman_ford(int start)
{
    for(int i = 1 ; i <= n ; i++)
    i == start ? dist[i] = 0 : dist[i] = INF ;
    for(int i = 1 ; i < n ; i++)
    {
        bool flag = false ;
        for(int j = 0 ; j < cnt ; j++)
        {
            int u = edge[j].u,v = edge[j].v,w = edge[j].w ;
            if(dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w ;
                flag = true ;
            }
        }
        if(!flag)
        return true ;
    }
    for(int j = 0 ; j < cnt ; j++)
    {
        int u = edge[j].u,v = edge[j].v,w = edge[j].w ;
        if(dist[v] > dist[u] + w)
        return false ;
    }
    return true ;
}
int main()
{
    char ch ;
    int u,v,w ;
    while(~scanf("%d %d",&n,&m))
    {
        cnt = 0 ;
        for(int i = 0 ; i < m ; i++)
        {
            getchar() ;
            scanf("%c",&ch) ;
            if(ch == ‘P‘)
            {
                scanf("%d %d %d",&u,&v ,&w) ;
                addedge(v,u,-w) ;
                addedge(u,v,w) ;
            }
            if(ch == ‘V‘)
            {
                scanf("%d %d",&u,&v) ;
                addedge(v,u,-1) ;
            }
        }
        if(bellman_ford(1)) printf("Reliable\n") ;
        else printf("Unreliable\n") ;
    }
    return 0 ;
}

Is the Information Reliable?(差分约束)

原文：http://www.cnblogs.com/You-Change/p/3531640.html