AMBIG - Words on graphs
Input
The input is a directed (multi)graph.
The first line gives the number of edges M and the number of nodes N (>=2). Then each edge is described by a line of the form "FROM TO LABEL". Nodes (FROM, TO) are numbers in the range 0 .. N-1 and labels are also numbers.
All numbers in the input are non-negative integers less then 2000.
Output
Print "YES" if there are two distinct walks with the same labelling from node 0 to node 1, otherwise print "NO".
Example 1
Input:
4 4
0 2 0
0 3 0
2 1 1
3 1 2
Output:
NO
Example 2
Input:
10 9
0 2 0
2 1 0
2 3 0
3 4 0
4 2 0
2 5 0
5 6 0
6 7 0
7 8 0
8 2 0
Output:
YES
In this case the shortest labelling that appears on two walks is 0 repeated 10 times.
hide comments
Aleksa:
2011-06-27 11:33:55
Can valid path consist of different labelled edges? |
|
ebd:
2010-03-18 00:12:26
Are repeated edges considered distinct? What is the answer for: 2 2 0 1 0 0 1 0? |
|
Radu Grigore:
2009-10-01 22:14:25
Right. Thanks Adrian! |
|
Adrian Satja Kurdija:
2009-10-01 22:14:25
"In this case the shortest labelling that appears on two walks is 0 repeated 17 times."
|
|
Radu Grigore:
2009-10-01 22:14:25
Please let me know here http://www.spoj.pl/forum/viewtopic.php?f=29&t=6008&sid=76af1ddb393c37d56832b77b77af06ce of a better way to put pictures in problem statements. |
|
piyifan:
2009-10-01 22:14:25
In China mainland, I can't see the image from blogspot. |
|
Radu Grigore:
2009-10-01 22:14:25
By "distinct" I meant "not the same". Would "different" be better? |
|
[Trichromatic] XilinX:
2009-10-01 22:14:25
Does "two distinct walks" mean "two routes which don't share any edge"? Last edit: 2009-09-30 05:16:26 |
Added by: | Radu Grigore |
Date: | 2009-09-29 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL GOSU NODEJS PERL6 VB.NET |
Resource: | S Even, On Information Lossless Automata of Finite Order, 1965 |