2013
11-12

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

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

Unreliable
Reliable

//* @author:
import java.io.*;
import java.util.Scanner;
/*
*SPFA 解决差分约束问题.一开始没另加源点一直WA....- -!~~~~
*/

class Node
{
int dian,value;
Node next;
Node(int x,int h)
{
dian=x;
value=h;
next=null;
}
void insert(Node a)
{
next=a;
}
}

class Point
{
int dian;
Node head;
Node last;
Point(int d)
{
dian=d;
head=new Node(0,0);
last=head;
}
void insert(Node a)
{
last.insert(a);
last=last.next;
}
}

class Quen
{
int front,rear,num;
int data[];
boolean include[];

Quen(int n)
{
front=rear=0;
num=n+1;
data=new int[n+1];
include=new boolean[n+1];
for(int i=0;i<=n;i++)include[i]=false;
}

boolean isEmpty()
{
if(rear==front)return true;
return false;
}

boolean add(int s)
{
if(include[s])return false;
data[rear]=s;
include[s]=true;
rear=(++rear)%num;
return true;
}

int get()
{
int s=data[front];
include[s]=false;
front=(++front)%num;
return s;
}
}

class SPFA
{
int numOfD;
int distance[],count[];
Point dian[];
Quen q;

SPFA(int n,Point s[])
{
numOfD=n;
dian=s;
q=new Quen(n);
distance=new int[numOfD+1];
count=new int[numOfD+1];
}

boolean haveMin()
{
q.add(0);
int now,i;
Node p;
for(i=1;i<=numOfD;i++)
{
distance[i]=Integer.MAX_VALUE;
count[i]=0;
}
distance[0]=0;
count[0]=1;
while(true)
{
if(q.isEmpty())break;
now=q.get();
p=dian[now].head;
while(p.next!=null)
{
p=p.next;
if(distance[p.dian]>distance[now]+p.value)
{
distance[p.dian]=distance[now]+p.value;
if(q.add(p.dian))
{
count[p.dian]++;
if(count[p.dian]==numOfD)return false;
}
}
}
}
return true;
}
}

public class Main {
public static void main(String args[]) throws IOException
{
Scanner cin=new Scanner(System.in);
int n,m,i,x,y,h;
String str;
SPFA data;
Point points[];
Node temp;
boolean ok;
while(cin.hasNextInt())
{
n=cin.nextInt();
m=cin.nextInt();
points=new Point[n+1];
points[0]=new Point(0);
for(i=1;i<=n;i++)
{
points[i]=new Point(i);
temp=new Node(i,0);
points[0].insert(temp);
}
for(i=0;i< m;i++)
{
str=cin.next();
if(str.charAt(0)=='P')
{
x=cin.nextInt();
y=cin.nextInt();
h=cin.nextInt();
temp=new Node(x,h);
points[y].insert(temp);
temp=new Node(y,-h);
points[x].insert(temp);
}
else
{
x=cin.nextInt();
y=cin.nextInt();
temp=new Node(y,-1);
points[x].insert(temp);
}
}
data=new SPFA(n,points);
ok=data.haveMin();
if(ok)System.out.println("Reliable");
else System.out.println("Unreliable");
}
}
}