Problem J
Brýr
Languages
en
is
ja
As everyone knows from last year, Eva and Stefán live in Vestmannaeyjar. You helped Eva find the best travel plan to tour the entire country with Stefán in the least amount of time. Now Eva wants to visit Egilsstaðir, but travelling around the country lead to them finding out that Stefán HATES single-lane bridges. Thus Eva looks to you once more to keep Stefán in a good mood.
Can you help Eva find the way from Vestmannaeyjar to Egilsstaðir using the least amount of single-lane bridges?
Input
On the first line there are two integers, $2 \leq n \leq 10^5$, the number of locations, and $n-1 \leq m \leq \min {(2\cdot 10^5, n(n-1)/2)}$, the number of roads. Next there are $m$ lines, each with three integers $1 \leq a, b \leq n$ and $c \in \{ 0, 1\} $ which means there is a road between location $a$ and location $b$ which contains a single-lane bridge if $c = 1$ but a double-lane bridge if $c = 0$. Vestmannaeyjar will always be location $1$ and Egilstaðir location $n$. You can assume Iceland’s road system is connected, i.e. it’s possible to get from any location to any other. You can also assume that any pair $a, b$ appears at most once in the input.
Output
One line containing the minimal number of single-lane bridges Stefán and Eva have to cross to get to their destination.
Scoring
|
Group |
Points |
Constraints |
|
1 |
20 |
$1 \leq n \leq 100$, $n = m$, Iceland’s road system consists of a single cycle of single-lane bridges ($c = 1$) |
|
2 |
20 |
$1 \leq n \leq 100$, all roads contain a single-lane bridge ($c = 1$) |
|
3 |
20 |
$1 \leq n \leq 100$ |
|
4 |
20 |
All roads contain a single-lane bridge ($c = 1$) |
|
5 |
20 |
No further constraints |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 3 1 1 1 2 1 2 3 1 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 6 5 6 1 5 4 1 2 1 1 2 3 1 4 3 1 1 4 1 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 13 7 3 0 7 10 1 8 2 0 10 2 1 4 6 0 4 1 0 9 5 1 6 9 0 7 6 1 3 10 0 4 5 0 5 7 1 4 8 0 |
1 |
