首页 > 代码库 > POJ Is the Information Reliable?

POJ Is the Information Reliable?

 

B - Is the Information Reliable?
Time Limit:3000MS     Memory Limit:131072KB     64bit IO Format:%I64d & %I64u
Submit Status

Description

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.

Input

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

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”.

Sample Input

3 4P 1 2 1P 2 3 1V 1 3P 1 3 15 5V 1 2V 2 3V 3 4V 4 5V 3 5

Sample Output

UnreliableReliable

#include <stdio.h>#include <string.h>int n, m;int dis[1003];int cnt;struct N{    int u;    int v;    int w;}s[200003];void add(int u, int v, int w ){    s[cnt].u=u;    s[cnt].v=v;    s[cnt++].w=w;}void bellman_ford(){    memset(dis, 0, sizeof(dis));    int i, j;    for(i=1; i<=n; i++)    {        for(j=0; j<cnt; j++) //检查每条边        {            if( dis[s[j].v] > dis[s[j].u] + s[j].w )                dis[s[j].v] = dis[s[j].u]+s[j].w ;        }    }    for(i=0; i<cnt; i++)    {        if(dis[s[i].v] > dis[s[i].u]+s[i].w )        break;    }    if(i<cnt)        printf("Unreliable\n");    else        printf("Reliable\n");}int main(){    int i, j;    char ch;    int u, v, w;    while(scanf("%d %d%*c", &n, &m)!=EOF)    {        cnt=0;        for(i=0; i<m; i++ )        {            ch=getchar();            while(ch!=‘P‘ && ch!=‘V‘)            {                ch=getchar();            }            if(ch==‘P‘)            {                scanf("%d %d %d", &u, &v, &w );                add(u, v, -1*w);                add(v, u, w);            }            else            {                scanf("%d %d", &u, &v );                add(u, v, -1 );            }        }        bellman_ford();    }    return 0;}

 

POJ Is the Information Reliable?