Hide

# Problem GOrtest 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. Not every graph contains an ortest path, here are three small examples: ## 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