No.1601 With Animals into Institute
Problem Statement
Dr. Y.Y. loves animals. Around the institute where Dr. Y.Y. works, there are $N$ towns numbered $1, 2, \dots, N$, and the institute is located in town $N$. The towns are connected by $M$ bidirectional roads, and the $j$-th road has length $C_j$ and connects town $A_j$ and town $B_j$. Also, it is possible to travel from any town to any town by passing through some number of roads.
Friendly animals inhabit this region, and when you pass through a road with an animal on it, the animal that was there comes along with you. Also, there is an animal on at least $1$ road.
Researchers live in towns $1, 2, \dots, N - 1$ and are about to commute to the institute, and they intend to bring $1$ or more animals with them to please Dr. Y.Y. However, if they take too much of a detour, they might be late. For each researcher, find, among the routes from town $i$ $(1 \le i \le N - 1)$ to town $N$ that pass through a road with an animal at least $1$ time, one that minimizes the total length of the roads. Note that each route may pass through the same town or the same road multiple times, and it is also possible to pass through town $N$ along the way without reporting to the institute.
Input
$N$ $M$
$A_1\ \ B_1\ \ C_1\ \ X_1$
$A_2\ \ B_2\ \ C_2\ \ X_2$
$\vdots$
$A_M\ \ B_M\ \ C_M\ \ X_M$
- $2 \le N \le 10^5$
- $1 \le M \le 2 \times 10^5$
- $1 \le A_j, B_j \le N,\ A_j \neq B_j \ \ (1 \le j \le M)$
- $1 \le C_j \le 10^9 \ \ (1 \le j \le M)$
- $X_j \in \{0, 1\} \ \ (1 \le j \le M)$
- The towns are numbered $1, 2, \dots, N$.
- The roads are numbered $1, 2, \dots, M$.
- Road $j$ connects town $A_j$ and town $B_j$ bidirectionally, and its length is $C_j$.
- $X_j$ represents the number of animals on road $j$, and there exists at least $1$ index $j$ such that $X_j = 1$.
- It is possible to reach any town from any town by passing through some number of roads.
- All inputs are integers.
Output
Output over $N - 1$ lines.
On the $i$-th line, output the minimum total length of the roads among the routes from town $i$ to town $N$ that pass through a road with an animal at least $1$ time. Under the settings and input constraints of this problem, it is guaranteed that such a route always exists.
Sample
Sample 1
Input
3 3 1 2 3 1 1 3 1 1 2 3 1 0
Output
1 3
There are animals on road $1$ and road $2$.
From town $1$, moving $1 \to 3$ via road $2$ reaches town $3$ with an animal at length $1$, and this is the shortest.
From town $2$, moving $2 \to 1 \to 3$ via roads $1, 2$ satisfies the condition with length $4$, but moving $2 \to 3 \to 1 \to 3$ via roads $3, 2, 2$ satisfies the condition with length $3$. Note that you may pass through the same town or road multiple times.
Sample 2
Input
4 6 1 2 4 1 1 3 2 0 1 4 1 1 2 3 2 0 3 4 1 0 3 4 4 1
Output
1 5 3
There may be multiple roads connecting the same pair of towns.
Sample 3
Input
7 15 2 1 5 1 3 7 10 1 1 5 6 1 5 1 10 1 7 4 8 0 2 4 4 0 7 1 7 0 3 7 3 0 2 3 7 1 1 7 8 0 1 3 6 1 7 2 6 0 5 3 9 0 1 6 3 0 2 5 5 0
Output
9 10 10 14 13 12
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。