No.1602 With Animals into Institute 2
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$. It is possible to travel from any town to any town by passing through some roads.
$K$ kinds of animals live in this region, and the kinds of animals are represented by the integers $1, 2, \dots, K$. On each road, there is at most $1$ animal of each kind. The animals are friendly: when you pass through a road with an animal on it, the animal that was there comes along with you. However, since each animal prefers animals of its own kind to humans, if you pass through a road with animal $k$ on it while accompanied by animal $k$, the animals $k$ that have met go off somewhere together.
Researchers live in towns $1, 2, \dots, N - 1$ and are about to commute to the institute, and in order to please Dr. Y.Y., they want to bring $1$ or more animals with them. However, if they make too long a detour, they may be late. For each researcher, among the routes from town $i$ $(1 \le i \le N - 1)$ to town $N$ such that the researcher has at least $1$ animal with them upon arriving at the institute, find one that minimizes the total length of the roads. However, the researchers here are not all that good-natured, so each route is not allowed to pass through the same town or the same road multiple times. Also, there are no animals inside the towns, each researcher has no animals at the time of departure, and the route of each researcher should be considered independently (ignoring any effects of the other researchers' movements).
Input
$N$ $M$ $K$
$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 K \le 30$
- $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)$
- Each $X_j$ is a string of length $K$ consisting of
0and1. - 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$.
- The $k$-th character from the left of $X_j$ represents the number of animals of kind $k$ on road $j$.
- It is possible to reach any town from any town by passing through some roads.
- All input values are integers, except for $X_j \ (1 \le j \le M)$.
Output
Print over $N - 1$ lines.
On the $i$-th line, print the minimum total length of the roads among routes such that the researcher has at least $1$ animal with them upon arriving at the institute, going from town $i$ to town $N$. For each $i$ for which no route satisfying the condition exists, print $-1$ instead.
Sample
Sample 1
Input
3 3 1 1 2 3 1 1 3 1 1 2 3 1 0
Output
1 -1
There is only $1$ kind of animal, and it is on road $1$ and road $2$.
From town $1$, moving $1 \to 3$ through road $2$ reaches town $3$ with an animal at length $1$, and this is the shortest.
From town $2$, if you move $2 \to 1 \to 3$ through roads $1, 2$, the animal $1$ that came along on road $1$ and the animal $1$ on road $2$ go off somewhere together, so the condition is not satisfied. Moving $2 \to 3$ through road $3$ does not satisfy the condition either, since there are no animals on road $3$. These $2$ are the only routes from town $2$ to town $3$, so print $-1$. Note that you must not pass through the same town or road multiple times.
Sample 2
Input
4 6 2 1 2 4 11 1 3 2 10 1 4 1 10 2 3 2 00 3 4 1 00 3 4 4 01
Output
1 5 4
There may be multiple roads connecting the same pair of towns.
Sample 3
Input
8 15 3 3 2 2 000 5 7 4 011 8 3 8 000 3 7 4 000 2 4 7 010 7 1 1 110 3 1 10 000 5 1 10 100 2 5 8 010 6 1 1 011 2 1 6 010 6 1 10 010 6 4 8 101 2 1 6 101 4 2 6 001
Output
13 19 -1 16 16 14 17
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。