uva12519

The Farnsworth Parabox

Professor Farnsworth, a renowned scientist that lives in year 3000 working at Planet Express Inc., performed a failed experiment that nearly killed him. As a sub-product, some strange boxes were created. Farnsworth gave one of the boxes to Leela, who accidentally discovered that it leads to a parallel universe. After that, the Planet Express crew traveled to the new discovered parallel universe using the box, meeting their corresponding parallel copies, including a parallel Professor Farnsworth who also created some boxes.

Simultaneously, some parallel copies of the Professor created similar boxes in some existing parallel universes. As a result, some universes, including the original one, were endowed with a (possibly empty) collection of boxes leading to other parallel universes. However, the boxes have a bug: besides allowing travels among different parallel universes, they allow for time travels. So, a particular box leads to a distinct parallel universe possibly allowing a voyager to gain or lose a certain number of time units.

One of the boxes invented by Farnsworth Professor, from Futurama. ©The Curiosity Company and 20^thCentury Fox.

More precisely, given two distinct universes A and B, and a non-negative integer number t, a (A, B)-box with time displacement t is an object designed to travel between the two universes that can be used directly (traveling from A to B) or reversely (traveling from B to A). A such box exists in both universes, allowing travels among both universes. A voyager that uses the (A, B)-box directly can travel from universe A to universe B landing t time units in the future. On the other hand, a voyager that uses the (A, B)-box reversely can travel from universe B to universe A landing t time units in the past. Box building requires so much energy that there may be built at most one box to travel between a given pair of different universes.

A circuit is defined as a non-empty sequence of parallel universes $left<vphantom{s_1,s_2,ldots,s_m} ight.$ s₁, s₂,..., s_m $left.vphantom{s_1,s_2,ldots,s_m} ight>$ such that:

The first and the last universe in the sequence are the same (i.e., s₁ = s_m).
For every k ( 1 k < m) there is a (s_k, s_k+1)-box or a (s_k+1, s_k)-box to travel (directly or reversely) from universe s_k to universe s_k+1.

The possible existence of circuits is very interesting. Using the corresponding boxes of a circuit, a voyager may experiment real time travels. Professor Farnsworth wants to know if there is a circuit that starts in the original universe and allows travels to the past, constituting a phenomenon known as the Farnsworth Parabox. For example, imagine that there are three universes, A, B and C, and that there exist the following boxes: a (A, B)-box with time displacement 3, a (A, C)-box with time displacement 2, and a (B, C)-box with time displacement 4. Clearly, the sequence A, B, C, A is a circuit, that allows to travel five time units in the future, starting and ending at universe A.

The original Farnsworth Professor, who lives in the original universe, wants to know if the Farnsworth Parabox is true or not. Can you help him?

Input

There are several cases to solve. Each case begins with a line with two integer numbers N and B, indicating the number of parallel universes (including the original) and the number of existing boxes, respectively ( 2 N 10², 1 B N^.(N - 1)/2). The distinct universes are identified uniquely with the numbers 1, 2,..., N, where the original universe is the number 1. Each one of the next B lines contains three integer numbers i, j and t, describing a (i, j)-box to travel between the universe i and the universe j with time displacement t (1iN, 1 j N, i j, 0 t 10²). The input ends with a line with two 0 values.

Output

For each test case output one line with the letter `Y' if the Farnsworth Parabox is true; or with the letter `N', otherwise.

Sample Input

Sample Output

N
Y
N

找不为0的环：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <queue>
 5 #include <math.h>
 6 #include <set>
 7 #include <vector>
 8 using namespace std;
 9 int n,m;
10 vector<pair<int,int> >a[150];
11 int b[150];
12 int c[150];
13 int dfs(int x,int z)
14 {
15     if(b[x])
16     {
17         if(c[x]!=z)
18         return 1;
19         else return 0;
20     }
21     c[x]=z;
22     b[x]=1;
23     int i;
24     int size=a[x].size();
25     for(i=0;i<size;i++)
26     {
27         if(dfs(a[x][i].first,z+a[x][i].second))return 1;
28     }
29     return 0;
30 }
31 int main()
32 {
33     //freopen("int.txt","r",stdin);
34     int i;
35     while(scanf("%d%d",&n,&m))
36     {
37         if(n==0&&m==0)break;
38         memset(b,0,sizeof(b));
39         memset(c,0,sizeof(c));
40         for(i=1;i<=n;i++)
41         a[i].clear();
42         int x,y,z;
43         for(i=0;i<m;i++)
44         {
45             scanf("%d%d%d",&x,&y,&z);
46             a[x].push_back(make_pair(y,z));
47             a[y].push_back(make_pair(x,-z));
48         }
49         if(dfs(1,0))
50         cout<<"Y"<<endl;
51         else cout<<"N"<<endl;
52     }
53 }

View Code