Dungeon Attack (Easy)

2 secs 1024 MB
magurofly

問題文


Dungeon Attack (Easy)Dungeon Attack (Hard) は同じ問題で、制約だけが異なります。

Dungeon Attack (Easy) 点、 Dungeon Attack (Hard) 点で、両方解くと 点になります。

アナウンス


  • 05/01 00:07: 入力の の間違いだったため修正しました。
  • 05/01 00:32: スタート地点とゴール地点が明記されていなかったため修正しました。
  • 05/01 12:09: 問題文が曖昧だったため追記しました。

ストーリー


高橋くんはダンジョンに挑みます。

このダンジョンには制限時間があり、 分以内に地点 にあるスタートから地点 にあるゴールにたどり着けば攻略成功となり、それまでに獲得したスコア分のお金をもらえます。

しかし、制限時間内にゴールにたどり着けなければ攻略失敗となり、それまでに稼いでいたスコアに関わらずお金はもらえません。

ダンジョン内部は迷路となっていて、 個の地点があり 本の道があります。

番目の道は地点 から への一方通行の道で、通るには 分かかります。 スコア が決まっていて、道を 回通るごとにもらえます。 このスコアは負のこともあります。

高橋くんはどの地点でも 分以上滞在することができます。

高橋くんが地点 からスタートするとき、最大でどれだけのスコアを稼いでゴール地点 に行くことができるか求めてください。

なお、ゴール地点にたどり着いても、制限時間内であれば他の頂点へ行くことができます。

ただし、一度ゴールにたどり着いても、ゴールにいない状態で制限時間が経過すると攻略失敗となります。

制約


  • 多重辺や自己ループは存在しない (ある頂点から出てある頂点に入る辺は高々 本であり、両端が同じ頂点であるような辺は存在しない)
  • 入力はすべて整数である

入力


出力


答えを 行に出力せよ。

入出力例


入力例1
3 3 5
1 2 1
2 3 2
3 2 3
出力例1
8

と進むことでスコア を稼いで 分でゴールすることができます。

しかし制限時間に余裕があるため、さらに と進むとスコア を稼いで 分でゴールすることができます。

入力例2
2 1 100
1 2 -10
出力例2
0

ゴールしても損しかしないため、制限時間まで待ったほうが得です。

Submit


Go (1.14)