Hide

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.

\includegraphics[width=0.8\textwidth ]{img/ortestpath-img-yes.pdf}

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

\includegraphics[width=0.6\textwidth ]{img/ortestpath-img-no.pdf}

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.

Gruppe

Point

Begrænsninger

1

18

$G$ er selv en vej, dvs. $G$ består af kanterne mellem $i$ og $i+1$ for $i\in \{ 0,\ldots , n - 2\} $

2

19

$G$ indeholder ingen kreds

3

20

$G$ indeholder en orteste vej af voksende knudenumre

4

21

$G$ indeholder højst én kant af vægt $1$

5

22

ingen yderligere begrænsninger

Sample Input 1 Sample Output 1
4 3 0 3
0 1 0
1 2 1
2 3 0
0 1 2 3 
Sample Input 2 Sample Output 2
4 3 0 3
0 1 1
1 2 0
1 3 0
0 1 3 
Sample Input 3 Sample Output 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 
Sample Input 4 Sample Output 4
4 3 3 1
0 1 1
2 3 0
1 2 0
-1
Sample Input 5 Sample Output 5
4 3 0 3
0 1 0
1 2 1
1 3 0
-1
Sample Input 6 Sample Output 6
5 5 0 2
0 1 0
1 2 0
1 3 0
1 4 0
3 4 1
-1

Please log in to submit a solution to this problem

Log in