Dungeon Attack (Hard)

2 secs 1024 MB
magurofly's icon magurofly

問題文

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

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

アナウンス

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

ストーリー

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

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

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

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

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

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

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

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

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

制約

  • 1N2001 \le N \le 200
  • 0MN20 \le M \le N^2
  • 1Ai,BiN1 \le A_i, B_i \le N
  • Si109|S_i| \le 10^9
  • 0T1090 \le T \le 10^9
  • 多重辺や自己ループは存在しない (ある頂点から出てある頂点に入る辺は高々 11 本であり、両端が同じ頂点であるような辺は存在しない)
  • 入力はすべて整数である

入力

N M TA1 B1 S1AM BM SMN\ M\ T\\ A_1\ B_1\ S_1\\ \vdots\\ A_M\ B_M\ S_M

出力

答えを 11 行に出力せよ。

入出力例

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

1231\to2\to3 と進むことでスコア 33 を稼いで 22 分でゴールすることができます。

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

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

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

提出


Go (1.21)