Hide

Ortest Path

Consider an undirected graph where each edge $e$ is labelled by a truth value $b(e)\in \{ 0,1\} $, where we interpret $0$ as false and $1$ as true. An ortest path is a simple path whose disjunction (Boolean “or”, $\vee $) is $1$, i.e., where $b(v_1v_2) \vee \dots \vee b(v_{k-1}v_ k) = 1$. Recall that a simple path from $v_1$ to $v_ k$ in a graph is a sequence of adjacent unique vertices $v_1$,$\ldots $, $v_ k$. Also recall that $0\vee 0 = 0$ and $0\vee 1 = 1\vee 0= 1\vee 1= 1$.

Given vertices $s$ and $t$, find an ortest path from $s$ to $t$. Below are three examples. Except for $G_1$, the drawings omit vertex indices and edge labels $0$ for readability. An ortest path from $s$ to $t$ is emphasized; note that $G_3$ contains many ortest paths.

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

Not every graph contains an ortest path, here are three small examples:

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

Input

The input starts with a line containing four non-negative integers: the number $n \in \{ 2,\ldots , 10\, 000\} $ of vertices, the number $m \in \{ 1,\ldots , 30\, 000\} $ of edges, and the indices of $s$ and $t$ with $s\neq t$. Vertices are indexed from $\{ 0, \ldots , n-1\} $. Then follow $m$ lines, each consisting of three integers $u$, $v$, and $b$, where $0 \leq u < v < n$ and $b\in \{ 0,1\} $, meaning that there is an undirected edge between $u$ and $v$ labeled $b$. No edge appears more than once in this list.

Output

Print a sequence of vertex indices $v_1$, $\ldots $, $v_ k$ separated by whitespace, such that $v_1=s$, $v_ k= t$, no vertex appears more than once, there is an edge between $v_ i$ and $v_{i+1}$ for each $i\in \{ 0,\ldots , k-1\} $, and $b(v_1v_2) \vee \dots \vee b(v_{k-1}v_ k) = 1$. If no such path exists, print $-1$.

Scoring

There are five test groups.

Group

Points

Constraints

1

18

$G$ is the path consisting of an edge between $i$ and $i+1$ for $i\in \{ 0,\ldots , n - 2\} $

2

19

$G$ does not contain a cycle

3

20

$G$ contains an ortest path of increasing vertex indices

4

21

$G$ contains at most one edge with label $1$

5

22

no restrictions

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
CPU Time limit 2 seconds
Memory limit 1024 MB
Difficulty 4.5 - 8.9hard
Statistics Show
Languages Dansk, English
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in