POJ 2983 Is the Information Reliable

The galaxy war between the Empire Draco and the Commonwealth of Zibu broke out 3 years ago. Draco established a line of defense called Grot. Grot is a straight line with N defense stations. Because of the cooperation of the stations, Zibu’s Marine Glory cannot march any further but stay outside the line.

A mystery Information Group X benefits form selling information to both sides of the war. Today you the administrator of Zibu’s Intelligence Department got a piece of information about Grot’s defense stations’ arrangement from Information Group X. Your task is to determine whether the information is reliable.

The information consists of M tips. Each tip is either precise or vague.

Precise tip is in the form of P A B X, means defense station A is X light-years north of defense station B.

Vague tip is in the form of V A B, means defense station A is in the north of defense station B, at least 1 light-year, but the precise distance is unknown.

There are several test cases in the input. Each test case starts with two integers N (0 < N ≤ 1000) and M (1 ≤ M ≤ 100000).The next M line each describe a tip, either in precise form or vague form.

Output one line for each test case in the input. Output “Reliable” if It is possible to arrange N defense stations satisfying all the M tips, otherwise output “Unreliable”.

#include <stdio.h>
#include <string.h>
#include <math.h>
struct num
{
    int end,next,val;
}a[1000000];
int b[10010],sum[10010],d[10010],status[10010];
int queue[1000000];
int INF=0x7fffffff,n;
int main()
{
    int spfa();
    int i,j,m,s,t,x,y,val,k;
    char c;
    while(scanf("%d %d%*c",&n,&m)!=EOF)
    {
        memset(b,-1,sizeof(b));
        for(i=1,j=0;i<=n;i++)
        {
            a[j].end=i;
            a[j].val=0;
            a[j].next=b[0];
            b[0]=j; j++;
        }
        for(i=0;i<=m-1;i++)
        {
            scanf("%c %d %d",&c,&x,&y);
            if(c=='P')
            {
                scanf("%d%*c",&val);
                a[j].end=y;
                a[j].val=-1*val;
                a[j].next=b[x];
                b[x]=j; j++;
                a[j].end=x;
                a[j].val=val;
                a[j].next=b[y];
                b[y]=j; j++;
            }else
            {
                getchar();
                a[j].end=y;
                a[j].val=-1;
                a[j].next=b[x];
                b[x]=j; j++;
            }
        }
        k=spfa();
        if(k)
        {
            printf("Reliable\n");
        }else
        {
            printf("Unreliable\n");
        }
    }
    return 0;
}
int spfa()
{
    int i,j,base,top,x,xend,k;
    k=1;
    memset(status,0,sizeof(status));
    memset(sum,0,sizeof(sum));
    for(i=1;i<=n;i++)
    {
        d[i]=INF;
    }
    base=top=0;
    d[0]=0;
    status[0]=1;
    sum[0]=1;
    queue[top++]=0;
    while(base<top)
    {
        x=queue[base++];
        status[x]=0;
        for(j=b[x];j!=-1;j=a[j].next)
        {
            xend=a[j].end;
            if(d[xend]>(d[x]+a[j].val))
            {
                d[xend]=d[x]+a[j].val;
                if(!status[xend])
                {
                    status[xend]=1;
                    queue[top++]=xend;
                    if(sum[xend]<=n-1)
                    {
                        sum[xend]+=1;
                    }else
                    {
                        k=0;
                        break;
                    }
                }
            }
        }
        if(j!=-1)
        {
            break;
        }
    }
    return k;
}