問題一覧 > 通常問題

No.1601 With Animals into Institute

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 54
作問者 : 👑 ygussanyygussany / テスター : shotoyooshotoyoo
2 ProblemId : 6406 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-09 23:17:14

問題文

Y.Y. 博士は動物が大好きです. Y.Y. 博士の居る研究所周辺には $1, 2, \dots, N$ の番号が付いた $N$ 個の街があり,研究所は街 $N$ の中にあります. 街同士は双方向に通行可能な $M$ 本の道で結ばれており,$j$ 番目の道は長さ $C_j$ で街 $A_j$ と街 $B_j$ を結んでいます. また,任意の街から任意の街に,道を何本か経由することで移動できます.

この地方には人懐こい動物が生息しており,動物の居る道を通るとそこに居た動物は一緒についてきます. また,少なくとも $1$ 本の道に動物が居ます.

街 $1, 2, \dots, N - 1$ には研究員が住んでおり,これから研究所に出勤しようとしていますが,Y.Y. 博士を喜ばせるために $1$ 匹以上の動物を連れていこうと考えています. しかし,あまり遠回りしていると遅刻してしまうかもしれません. それぞれの研究員のために,街 $i$ $(1 \le i \le N - 1)$ から街 $N$ への移動経路であって,動物の居る道を少なくとも $1$ 回通るようなもののうち,道の長さの総和が最小となるものを求めてあげてください. ただし,各移動経路では同じ街や同じ道を複数回経由してもよいものとし,途中で研究所に出勤しないで街 $N$ を素通りすることも可能であるとします.

入力

$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)$
  • 街には $1, 2, \dots, N$ の番号が付いている.
  • 道には $1, 2, \dots, M$ の番号が付いている.
  • 道 $j$ は街 $A_j$ と街 $B_j$ を双方向に結び,その長さは $C_j$ である.
  • $X_j$ は道 $j$ に居る動物の数を表し,$X_j = 1$ であるような $j$ が少なくとも $1$ つ存在する
  • 任意の街から任意の街に,道を何本か経由することで到達可能である.
  • 入力は全て整数である.

出力

$N - 1$ 行に渡って出力してください.

$i$ 行目には,動物の居る道を少なくとも $1$ 回通るような街 $i$ から街 $N$ への移動経路における道の長さの総和の最小値を出力してください. 本問題の設定と入力制約の下では,そのような移動経路が必ず存在することが保証されます.

サンプル

サンプル 1
入力
3 3
1 2 3 1
1 3 1 1
2 3 1 0
出力
1
3

動物は道 $1$ と道 $2$ に居ます.

街 $1$ からは,道 $2$ を通って $1 \to 3$ と移動すれば長さ $1$ で動物を連れて街 $3$ に到達でき,これが最短です.

街 $2$ からは,道 $1, 2$ を通って $2 \to 1 \to 3$ と移動すれば長さ $4$ で条件を達成できますが,道 $3, 2, 2$ を通って $2 \to 3 \to 1 \to 3$ と移動することで長さ $3$ で条件を達成できます. 同じ街や道を複数回経由してもよいことに注意してください.

サンプル 2
入力
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
出力
1
5
3

同じ街のペアを結ぶ道が複数あることもあります.

サンプル 3
入力
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
出力
9
10
10
14
13
12

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。