|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
Hello 2016Ended |
H - Perfect Path
Languages: C, C++, Java, Haskell, JavaScript, Pascal, Tiger, Python, C#
Time & Memory limits: (details)
El laberinto de Amsterdam está compuesto por $n$ habitaciones y $m$ pasajes. Cada pasaje tiene un color $c_i$. Los visitantes son lanzados desde un helicóptero en la habitación $1$ y deben llegar a la $n$. El martes serán lanzados varios corredores en la habitación $1$. Cada uno de ellos corre hacia la habitación número $n$ escribiendo el color de los pasajes por los que pasan.
El ganador es el que tenga la secuencia de colores de menor tamaño. Si hay varios que tienen el mismo tamaño el que tenga la secuencia menor lexicográficamente gana.
Adrew se esta preparando para la competencia. El tiene una foto del laberinto desde el helicóptero, tu tarea es encontrar el camino óptimo desde la habitacion $1$ hasta la $n$.
Nota:
Una sequencia $(A_1 , A_2, ..., A_n)$ es menor lexicográficamente que otra sequencia $(B_1 , B_2, ..., B_n)$ si existe $i$ tal que $A_i < B_i$ y $A_j = B_j$ para todo $j \lt i$.
El ganador es el que tenga la secuencia de colores de menor tamaño. Si hay varios que tienen el mismo tamaño el que tenga la secuencia menor lexicográficamente gana.
Adrew se esta preparando para la competencia. El tiene una foto del laberinto desde el helicóptero, tu tarea es encontrar el camino óptimo desde la habitacion $1$ hasta la $n$.
Nota:
Una sequencia $(A_1 , A_2, ..., A_n)$ es menor lexicográficamente que otra sequencia $(B_1 , B_2, ..., B_n)$ si existe $i$ tal que $A_i < B_i$ y $A_j = B_j$ para todo $j \lt i$.
Input
La primera línea de la entrada contiene los enteros $n$ $(n \le 100000)$ y $m$ $(m \le 200000)$, la cantidad de habitaciones y de pasajes respectivamente.
Las siguientes $m$ líneas describen los pasajes con tres números $a$ , $b$ y $c$, las habitaciones que conecta y el color del pasaje $(1 \le a,b \le n)$, $(1 \le c \le 10^9)$.
Cada pasaje puede ser transitado en cualquier dirección. Dos habitaciones pueden estar conectadas por más de un pasaje y puede haber un pasaje de una habitación a si misma.
Esta garantizado que se puede llegar desde la habitacion $1$ hasta la $n$.
Las siguientes $m$ líneas describen los pasajes con tres números $a$ , $b$ y $c$, las habitaciones que conecta y el color del pasaje $(1 \le a,b \le n)$, $(1 \le c \le 10^9)$.
Cada pasaje puede ser transitado en cualquier dirección. Dos habitaciones pueden estar conectadas por más de un pasaje y puede haber un pasaje de una habitación a si misma.
Esta garantizado que se puede llegar desde la habitacion $1$ hasta la $n$.
Output
La primera línea de la entrada contiene un entero $k$ , la cantidad longitud del menor camino.
La segunda línea contiene $k$ enteros, los colores de los pasajes en el orden en que deben ser transitados en el camino óptimo.
Sample test(s)
Input
4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1
Output
2
1 3