Problem G
Orteste vej

Betragt en urettet graf, i hvilken hver kant $e$ er vægtet med en sandhedsværdi $b(e)\in \{ 0,1\} $, hvor vi tolker $0$ og $1$ som henholdsvis falsk og sand. En orteste vej er en simpel vej, hvis disjunktion (boolsk »eller«, $\vee $) er $1$, dvs. at der gælder $b(v_1v_2) \vee \dots \vee b(v_{k-1}v_ k) = 1$. Husk at en simpel vej fra $v_1$ til $v_ k$ i en graf er en følge af knuder $v_1$, $\ldots $, $v_ k$ uden gentagelser, således at $v_ i$ og $v_{i+1}$ deler en kant. Husk også at $0\vee 0 = 0$ og $0\vee 1 = 1\vee 0= 1\vee 1= 1$.

Givet et par af knuder $s$ og $t$, find en orteste vej fra $s$ til $t$. Forneden er vist tre eksempler. For overskueligheden skyld er knudenumre og kantvægten $0$ kun vist i tegningen for $G_1$, men udeladt i de andre tegninger. En orteste vej fra $s$ til $t$ er fremhævet; bemærk at $G_3$ indeholder mange sådanne veje.

Der findes grafer uden en orteste vej, her er vist tre små eksempler:

Indlæsning

Indlæsningen begynder med en linje indeholdende fire ikke-negative heltal: antallet $n \in \{ 2,\ldots , 10\, 000\} $ af knuder, antallet $m \in \{ 1,\ldots , 30\, 000\} $ af kanter og numrene på $s$ og $t$, hvor $s\neq t$. Knudernes numre er mængden $\{ 0, \ldots , n-1\} $. Derpå følger $m$ linjer, hver bestående af tre heltal $u$, $v$ og $b$, hvor $0 \leq u < v < n$ og $b\in \{ 0,1\} $, som angiver, at der findes en urettet kant mellem $u$ og $v$ med vægt $b$. Ingen kant optræder mere end én gang på listen.

Udskrift

Skriv en følge af knudenumre $v_1$, $\ldots $, $v_ k$, adskilte af mellemrum, således at $v_1=s$, $v_ k= t$, ingen knude optræder mere end én gang, der findes en kant mellem $v_ i$ og $v_{i+1}$ for hvert $i\in \{ 0,\ldots , k-1\} $ og $b(v_1v_2) \vee \dots \vee b(v_{k-1}v_ k) = 1$. Hvis sådan en vej ikke findes, skriv $-1$.

Pointsætning

Der er fem testgrupper.

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

0 1 2 3 

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

0 1 3 

10 15 4 1
0 1 0
1 2 1
2 3 1
3 4 0
0 4 0
0 5 0
1 6 0
2 7 0
3 8 0
4 9 1
5 7 0
5 8 0
6 8 0
6 9 0
7 9 0

4 3 2 1 

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

-1

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

-1

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

-1