問題文
未来のArcaeaではWorld Modeが進化し、道が分岐したり、道に条件が存在するようになっています。
彩夢さんはArcaeaのWorldを進もうとしていますが、せっかくなのでAi-Chanのおすすめの曲でWorldを進むことにしました。
マップは以下のように与えられます:
- マスは個あり、からまで番号が振られています。
- マスがスタート地点で、マスがゴール地点です。
- マス同士をつなぐ道が本あり、各道は一方通行です。
- それぞれの道は、マスからマスに向かう道ですが、進むには難易度以上の曲をプレイする必要があります。
また、Ai-Chanのおすすめの曲は1回プレイするごとに変化します。
具体的には、
- 最初のプレイでは難易度・難易度・難易度の3曲、
- 2回目のプレイでは難易度・難易度・難易度の3曲、
- ...
- 回目のプレイでは難易度・難易度・難易度の3曲、
- 回目のプレイでは難易度・難易度・難易度の3曲、
- 回目のプレイでは難易度・難易度・難易度の3曲、
- ...
と言った具合に、回ごとにおすすめの曲がループします。
World Modeは以下のように進行します:
- まず、マスからスタートします。
- Ai-Chanのおすすめの曲の中から1曲を選び、その曲をプレイします。
- 現在いるマスから、進む道を1本選びます。
- 選んだ曲の難易度が、進む道の難易度以上であれば、その道を必ず進みます。
- もし選んだ曲の難易度が、進む道の難易度より低ければ、道を進むことはできません。
- ただし、この場合でもプレイ回数はカウントされます。
- 道を進んだ後、次のマスに到着します。
- これを繰り返し、マスに到着すればゴールです。
彩夢さんは可能な限り楽にマスに到着したいと考えています。 プレイする曲の難易度の合計を最小化するとき、マスに到着するまでにプレイした曲の難易度の合計の最小値を求めてください。
ただし、マスに到着できることは保証されています。
制約
- 入力される値はすべて整数
- マスに到着することが可能である。
入力
入力は以下の形式で標準入力から与えられます。
出力
マスに到着するまでの難易度の合計の最小値を1行で出力してください。
サンプル 1
入力
4 4 2
1 2 3
2 4 4
1 3 6
3 4 2
3 6 9
2 4 8
出力
7
このマップは以下のようになっています。(マスの中の数字はマスの番号、矢印の中の数字は道を進むのに必要な難易度です。)
例えば以下のようにプレイすると、難易度の合計はになります。
- 1回目:選べる曲は難易度・・の3曲です。難易度の曲を選び、マスからマスへの道を選びます。道に必要な難易度はなので、マスへ進むことができます。
- 2回目:選べる曲は難易度・・の3曲です。難易度の曲を選び、マスからマスへの道を選びます。道に必要な難易度はなので、マスへ進むことができます。
難易度の合計を以下にすることはできないため、答えはになります。
サンプル 2
入力
2 1 2
1 2 5
1 10 12
5 6 7
出力
6
例えば以下のようにプレイすると、難易度の合計はになります。
- 1回目:選べる曲は難易度・・の3曲です。難易度の曲をプレイして、マスからマスへの道を選びます。必要な難易度はなので、マスへ進むことができます。
しかし、以下のようにプレイすると、難易度の合計はになります。
- 1回目:選べる曲は難易度・・の3曲です。難易度の曲をプレイして、マスからマスへの道を選びます。必要な難易度はなので、マスに留まります。
- 2回目:選べる曲は難易度・・の3曲です。難易度の曲をプレイして、マスからマスへの道を選びます。必要な難易度はなので、マスへ進むことができます。
道を進めなかった場合も、おすすめは次の回に進むことに注意してください。 また、プレイ回数を最小化する必要はありません。
サンプル 3
入力
3 2 2
1 2 5
2 3 8
2 8 10
1 3 4
出力
17
以下のようにプレイすると、難易度の合計はになります。
- 1回目:選べる曲は難易度・・の3曲です。難易度の曲をプレイして、マスからマスへの道を選びます。必要な難易度はなので、マスへ進むことができます。
- 2回目:選べる曲は難易度・・の3曲です。難易度の曲をプレイして、マスからマスへの道を選びます。必要な難易度はなので、マスに留まります。
- 3回目: 選べる曲は難易度・・の3曲です。難易度の曲をプレイして、マスからマスへの道を選びます。必要な難易度はなので、マスへ進むことができます。
サンプル 4
入力
2 1 2
1 2 1
12 12 12
1 1 1
出力
12
難易度の曲を選び、マスからマスへ進む以外の選択肢はありません。
参加受付は終了しました。
ログインして解答を提出
解答の提出や採点結果の確認には、ログインが必要です。
ログインする