問題一覧 > 通常問題

No.1602 With Animals into Institute 2

レベル : / AI推定難易度 : 3500 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 13
作問者 : ygussany / テスター : shotoyoo
お気に入りにしたユーザー ProblemId : 6377 / 自分の提出
問題文最終更新日: 2022-04-26 09:23:09
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Y.Yさんの単発問題コンテスト (順位表) の他の問題:

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).

HintLet's meta-read the problem and its solution from the problem setter.
Hint?Here, what seems to be a relevant blog post...?
Hint??Here, what seems to be a relevant paper...?

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 0 and 1.
  • 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もしくは右上の雲マークをクリックしてアカウントを作成してください。