問題一覧 > 通常問題

No.1601 With Animals into Institute

レベル : / AI推定難易度 : 1325 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 79
作問者 : ygussany / テスター : shotoyoo
お気に入りにしたユーザー ProblemId : 6406 / 自分の提出
問題文最終更新日: 2022-04-26 09:22:51
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$. 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もしくは右上の雲マークをクリックしてアカウントを作成してください。