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 4 P 1 2 1 P 2 3 1 V 1 3 P 1 3 1 5 5 V 1 2 V 2 3 V 3 4 V 4 5 V 3 5
Sample Output
Unreliable Reliable
#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?
原文：http://www.cnblogs.com/yspworld/p/3930767.html