Problem G
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.
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 |