外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

G - Only World Mode with Ai-Chan

作成者 sevenc_nanashi

テスター unbakedbread

配点 450 点

実行時間制限
2.5 秒
メモリ制限
512 MiB

問題文

未来のArcaeaではWorld Modeが進化し、道が分岐したり、道に条件が存在するようになっています。

彩夢さんはArcaeaのWorldを進もうとしていますが、せっかくなのでAi-Chanのおすすめの曲でWorldを進むことにしました。

マップは以下のように与えられます:

  • マスはNN個あり、11からNNまで番号が振られています。
  • マス11がスタート地点で、マスNNがゴール地点です。
  • マス同士をつなぐ道がMM本あり、各道は一方通行です。
  • それぞれの道は、マスuiu_iからマスviv_iに向かう道ですが、進むには難易度wiw_i以上の曲をプレイする必要があります。

また、Ai-Chanのおすすめの曲は1回プレイするごとに変化します。
具体的には、

  • 最初のプレイでは難易度A1,1A_{1,1}・難易度A1,2A_{1,2}・難易度A1,3A_{1,3}の3曲、
  • 2回目のプレイでは難易度A2,1A_{2,1}・難易度A2,2A_{2,2}・難易度A2,3A_{2,3}の3曲、
  • ...
  • KK回目のプレイでは難易度AK,1A_{K,1}・難易度AK,2A_{K,2}・難易度AK,3A_{K,3}の3曲、
  • K+1K+1回目のプレイでは難易度A1,1A_{1,1}・難易度A1,2A_{1,2}・難易度A1,3A_{1,3}の3曲、
  • K+2K+2回目のプレイでは難易度A2,1A_{2,1}・難易度A2,2A_{2,2}・難易度A2,3A_{2,3}の3曲、
  • ...

と言った具合に、KK回ごとにおすすめの曲がループします。

World Modeは以下のように進行します:

  • まず、マス11からスタートします。
  • Ai-Chanのおすすめの曲の中から1曲を選び、その曲をプレイします。
  • 現在いるマスから、進む道を1本選びます。
    • 選んだ曲の難易度が、進む道の難易度以上であれば、その道を必ず進みます。
    • もし選んだ曲の難易度が、進む道の難易度より低ければ、道を進むことはできません。
    • ただし、この場合でもプレイ回数はカウントされます。
  • 道を進んだ後、次のマスに到着します。
  • これを繰り返し、マスNNに到着すればゴールです。

彩夢さんは可能な限り楽にマスNNに到着したいと考えています。 プレイする曲の難易度の合計を最小化するとき、マスNNに到着するまでにプレイした曲の難易度の合計の最小値を求めてください。

ただし、マスNNに到着できることは保証されています。

制約

  • 入力される値はすべて整数
  • 2≤N≤5×1042 \leq N \leq 5 \times 10^4
  • 1≤M≤5×1041 \leq M \leq 5 \times 10^4
  • 1≤K≤101 \leq K \leq 10
  • 1≤ui,vi≤N(1≤i≤M)1 \leq u_i, v_i \leq N \quad (1 \leq i \leq M)
  • ui≠vi(1≤i≤M)u_i \neq v_i \quad (1 \leq i \leq M)
  • 1≤wi≤12(1≤i≤M)1 \leq w_i \leq 12 \quad (1 \leq i \leq M)
  • 1≤Ai,1,Ai,2,Ai,3≤121 \leq A_{i,1}, A_{i,2}, A_{i,3} \leq 12
  • マスNNに到着することが可能である。

入力

入力は以下の形式で標準入力から与えられます。

NMKN \quad M \quad K u1v1w1u_1 \quad v_1 \quad w_1 u2v2w2u_2 \quad v_2 \quad w_2 ... uMvMwMu_M \quad v_M \quad w_M A1,1A1,2A1,3A_{1,1} \quad A_{1,2} \quad A_{1,3} A2,1A2,2A2,3A_{2,1} \quad A_{2,2} \quad A_{2,3} ... AK,1AK,2AK,3A_{K,1} \quad A_{K,2} \quad A_{K,3}

出力

マスNNに到着するまでの難易度の合計の最小値を1行で出力してください。

サンプル 1

入力

4 4 2
1 2 3
2 4 4
1 3 6
3 4 2
3 6 9
2 4 8

出力

7

このマップは以下のようになっています。(マスの中の数字はマスの番号、矢印の中の数字は道を進むのに必要な難易度です。)

マップの図

例えば以下のようにプレイすると、難易度の合計は77になります。

  • 1回目:選べる曲は難易度33・66・99の3曲です。難易度33の曲を選び、マス11からマス22への道を選びます。道に必要な難易度は33なので、マス22へ進むことができます。
  • 2回目:選べる曲は難易度22・44・88の3曲です。難易度44の曲を選び、マス22からマス44への道を選びます。道に必要な難易度は44なので、マス44へ進むことができます。

難易度の合計を66以下にすることはできないため、答えは77になります。

サンプル 2

入力

2 1 2
1 2 5
1 10 12
5 6 7

出力

6

例えば以下のようにプレイすると、難易度の合計は1010になります。

  • 1回目:選べる曲は難易度11・1010・1212の3曲です。難易度1010の曲をプレイして、マス11からマス22への道を選びます。必要な難易度は55なので、マス22へ進むことができます。

しかし、以下のようにプレイすると、難易度の合計は66になります。

  • 1回目:選べる曲は難易度11・1010・1212の3曲です。難易度11の曲をプレイして、マス11からマス22への道を選びます。必要な難易度は55なので、マス11に留まります。
  • 2回目:選べる曲は難易度55・66・77の3曲です。難易度55の曲をプレイして、マス11からマス22への道を選びます。必要な難易度は55なので、マス22へ進むことができます。

道を進めなかった場合も、おすすめは次の回に進むことに注意してください。 また、プレイ回数を最小化する必要はありません。

サンプル 3

入力

3 2 2
1 2 5
2 3 8
2 8 10
1 3 4

出力

17

以下のようにプレイすると、難易度の合計は8+1+8=178+1+8=17になります。

  • 1回目:選べる曲は難易度22・88・1010の3曲です。難易度88の曲をプレイして、マス11からマス22への道を選びます。必要な難易度は55なので、マス22へ進むことができます。
  • 2回目:選べる曲は難易度11・33・44の3曲です。難易度11の曲をプレイして、マス22からマス33への道を選びます。必要な難易度は88なので、マス22に留まります。
  • 3回目: 選べる曲は難易度22・88・1010の3曲です。難易度88の曲をプレイして、マス22からマス33への道を選びます。必要な難易度は88なので、マス33へ進むことができます。

サンプル 4

入力

2 1 2
1 2 1
12 12 12
1 1 1

出力

12

難易度1212の曲を選び、マス11からマス22へ進む以外の選択肢はありません。

参加受付は終了しました。