Poj 2983(差分制約システム)

やはりその言葉:差分制約問題の難点は「どのように問題の制約条件を見つけるか」です.
この問題で入力したエッジには2つのフォーマットがあります.
      1. エッジ長決定、すなわちxi−xj=b;xi-xj<=bおよびxi-xj>=b(すなわちxj-xi<=-b)に変換することができる.
      2. 辺長不定、xi-xj>=1;xj-xi<=-1に変換できます.
 
以下にSPFAアルゴリズムを用いて実現する.

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#define MAXV 1005  
#define MAXE 201005  
#define INF  100000000  
struct  
{  
    int  e, v;  
} edge[MAXE];  
int n, neg;  
int dis[MAXV], cnt[MAXV];  
int node[MAXV], next[MAXE];  
int Q[MAXV], vst[MAXV];  
void add(int s, int e, int v)  
{  
    edge[neg].e = e;  
    edge[neg].v = v;  
    next[neg] = node[s];  
    node[s] = neg++;  
}  
int relax(int s, int e, int v)  
{  
    if (dis[s]+v < dis[e])  
    {  
        dis[e] = dis[s]+v;  
        return 1;  
    }  
    return 0;  
}  
//     。  
int SPFA(int s0)  
{  
    int i, t, p, top;  
    memset(cnt, 0, sizeof(cnt));  
    memset(vst, 0, sizeof(vst));  
    for (i=0; i<=n; i++)  
        dis[i] = INF;  
    dis[s0] = 0;  
    Q[0] = s0;  
    top = 1;  
    vst[s0] = 1;  
    cnt[s0]++;  
    while (top)  
    {  
        t = Q[--top];  
        vst[t] = 0;  
        p = node[t];  
        while (p != -1)  
        {  
            if (relax(t, edge[p].e, edge[p].v) && !vst[edge[p].e])  
            {  
                Q[top++] = edge[p].e;  
                vst[edge[p].e] = 1;  
                cnt[edge[p].e]++;  
                if (cnt[edge[p].e] > n+1)  
                    return 0;  
            }  
            p = next[p];  
        }  
    }  
    return 1;  
}  
int main()  
{  
    int  m, a, b, c, i;  
    char f;  
    while (scanf("%d %d", &n, &m) != EOF)  
    {  
        neg = 0;  
        memset(node, -1, sizeof(node));  
        while (m--)  
        {  
            scanf("%*c %c %d %d", &f, &a, &b);  
            if (f == 'P')  
            {  
                scanf("%d", &c);  
                add(a, b, c);  
                add(b, a, -c);  
            }  
            else  
                add(b, a, -1);  
        }  
        //      0      
        for (i=1; i<=n; i++)  
            add(0, i, 1);  
        if (SPFA(0))  
            printf("Reliable/n");  
        else  
            printf("Unreliable/n");  
    }  
}