Semàfors P68618


Statement
 

pdf   zip

thehtml

Després d’una llarga partida a l’Age of Empires, els participants de la UPC decideixen anar a registrar-se per al SWERC abans que sigui massa tard. Per això han d’anar des de l’hotel fins a la universitat de Porto.

La ciutat té n illes (numerades entre 0 i n−1) i m passos de vianants. Cada pas de vianants és bidireccional, connecta dues illes diferents, i té un semàfor que està en verd o en vermell. Els semàfors canvien d’estat cada t segons, tots a la vegada. Suposant negligible el temps de creuar els passos de vianants amb el semàfor en verd, i que no es creuarà mai en vermell, quant es triga en anar des de l’illa 0 (l’hotel) fins a l’illa n−1 (la universitat)?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, m i t. Segueixen m triples x y c indicant que hi ha un pas de vianants entre les illes x i y, i que el semàfor corresponent inicialment està en verd si c és 0, o en vermell si c és 1. Assumiu 2 ≤ n ≤ 104, 0 ≤ m ≤ 5n, 1 ≤ t ≤ 50, x ≠ y, i que entre dues illes només hi haurà com a màxim un pas de vianants.

Sortida

Per a cada cas, escriviu el temps mínim d’anar des de 0 fins a n−1. Si no és possible anar des de 0 fins a n−1, escriviu “WOLOLO!!!”.

Public test cases

  • Input

    2 1 50
1 0 1

3 2 50
1 0 0
1 2 0

5 4 5
0 1 0
1 2 1
2 4 0
0 3 0

5 3 10
0 1 0
1 2 0
3 4 0

    Output

    50
0
10
WOLOLO!!!
    • Information
    Author
    Albert Martínez
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++