226. Colored graph
time limit per test: 0.25
sec.
memory limit per test: 4096
KB
input: standard
output: standard
You are given an oriented graph. Each edge of the graph is colored in one of the three colors. Your task is to find the length of the shortest path from the first vertex to the Nth. Note that any two successive edges in the path can't have the same color.
Input
The first line of the input file consists of two integers N and M (2 <= N <= 200; 0 <= M <= N*N). Next M lines contain descriptions of the edges. Each edge description is a list of three integers X, Y, C (1 <= X, Y <= N, 1 <= C <= 3), where X is the starting vertex of the edge, Y is the finishing vertex and C is the color of the edge.
Output
Output the length of the shortest path between the first and the Nth vertexes. Output "1" if the path doesn't exist.
Sample test(s)
Input
Test #1
4 4
1 2 1
2 3 2
3 4 3
2 4 1
Test #2
3 2
1 2 1
2 3 1
Output
Test #1
3
Test #2
1
Author:  

Resource:  

Date:  

Server time: 20170922 15:47:02  Online Contester Team © 2002  2016. All rights reserved. 

