問題一覧 > 通常問題

No.1602 With Animals into Institute 2

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

問題文

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

この地方には $K$ 種類の動物が生息しており,動物の種類は $1, 2, \dots, K$ の整数で表されます. 各道には,各種類の動物が高々 $1$ 匹居ます. 動物たちは人懐こく,動物の居る道を通るとそこに居た動物は一緒についてきます. ただし,各動物は人間よりも同種の動物の方を好むため,動物 $k$ を連れた状態で動物 $k$ の居る道を通ると,居合わせた動物 $k$ は連れ立ってどこかへ行ってしまいます

街 $1, 2, \dots, N - 1$ には研究員が住んでおり,これから研究所に出勤しようとしていますが,Y.Y. 博士を喜ばせるために $1$ 匹以上の動物を連れていこうと考えています. しかし,あまり遠回りしていると遅刻してしまうかもしれません. それぞれの研究員のために,街 $i$ $(1 \le i \le N - 1)$ から街 $N$ への移動経路であって,研究所に着いた時点で少なくとも $1$ 匹の動物を連れているようなもののうち,道の長さの総和が最小となるものを求めてあげてください. ただし,今回の研究員はそこまでお人好しではないので,各移動経路では同じ街や同じ道を複数回経由することは許さないものとします. また,街の中に動物は居らず,各研究員は出発時点で動物を一切連れていないものとし,移動経路は研究員ごとに独立に(他の研究員の移動による影響は無視して)考えてください.

ヒント作問者から問題と解法をメタ読みしましょう.
ヒント?こんなところにそれらしきブログ記事が…?
ヒント??こんなところにそれらしき論文が…?

入力

$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)$
  • 各 $X_j$ は 01 からなる長さ $K$ の文字列である.
  • 街には $1, 2, \dots, N$ の番号が付いている.
  • 道には $1, 2, \dots, M$ の番号が付いている.
  • 道 $j$ は街 $A_j$ と街 $B_j$ を双方向に結び,その長さは $C_j$ である.
  • $X_j$ の左から $k$ 文字目は道 $j$ に居る動物 $k$ の数を表す.
  • 任意の街から任意の街に,道を何本か経由することで到達可能である.
  • 入力は $X_j \ (1 \le j \le M)$ を除き全て整数である.

出力

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

$i$ 行目には,研究所に着いた時点で少なくとも $1$ 匹の動物を連れているような街 $i$ から街 $N$ への移動経路における道の長さの総和の最小値を出力してください. ただし,条件を満たす移動経路が存在しない $i$ に対しては $-1$ を出力してください.

サンプル

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

動物は $1$ 種類のみで,道 $1$ と道 $2$ に居ます.

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

街 $2$ からは,道 $1, 2$ を通って $2 \to 1 \to 3$ と移動すると,道 $1$ でついてきた動物 $1$ と道 $2$ に居る動物 $1$ が連れ立ってどこかへ行ってしまうため,条件を満たせません. また,道 $3$ を通って $2 \to 3$ と移動しても,道 $3$ には動物が居ないので,やはり条件を満たせません. 街 $2$ から街 $3$ への移動経路は以上の $2$ つのみなので,$-1$ を出力します. 同じ街や道を複数回経由してはいけないことに注意してください.

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

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

サンプル 3
入力
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
出力
13
19
-1
16
16
14
17

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