#codefestival2018finalh. [code_festival_2018_final_h]Pothunter
[code_festival_2018_final_h]Pothunter
問題文
AtCoder共和国は から までの番号がついた町と から の番号がついた 本の道からできています。それぞれの町は道をたどって到達可能です。
道 は町 と を双方向につなぐ道で、移動に だけ時間がかかります。
AtCoder共和国で から までの番号がついた 個のオンサイトコンテストが開催されることになりました。
コンテスト は町 で開催され、開始時刻は で終了時刻は です。また、コンテストの優勝賞金は 円です。
賞金稼ぎの高橋君は、賞金をできる限りたくさんもらいたいです。高橋君はとても強いので参加したコンテスト全てで優勝可能です。
高橋君がコンテスト に参加するためには、 を満たすいずれの時刻 においても町 にいて他のコンテストに参加していない必要があります。 詳しくはサンプル も参照してください。
高橋君が時刻 の時点で好きな位置にいることができるときの、高橋君が得られる賞金の総和の最大値を求めてください。
制約
- 与えられる入力は全て整数
- 全ての町は道を辿って到達可能
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
入力例 1
5 4
1 2 2
2 3 3
2 4 1
4 5 5
1 5 1 5
2 5 3 7
8 15 4 5
12 16 5 9
出力例 1
10
- 時刻 に町 にいる
- 時刻 まで留まる
- 時刻 に町 で開催されるコンテスト に参加する
- 時刻 に町 に向かって移動する
- 時刻 に町 に向かって移動する
- 時刻 に町 で開催されるコンテスト に参加する
- 得られる賞金の総和は となり、これが最大です
入力例 2
11 10
5 9 1
2 9 5
4 8 4
2 6 1
3 7 3
5 8 2
2 11 5
3 11 1
1 4 3
9 10 3
1 7 11 10
2 8 9 12
8 15 3 11
2 3 2 4
3 6 4 6
7 9 5 9
4 8 1 7
11 18 6 9
10 14 6 4
5 11 7 11
出力例 2
21
入力例 3
2 6
1 2 1000000000
1 2 1 1000000000
3 4 1 1000000000
5 6 1 1000000000
7 8 1 1000000000
899999999 900000000 1 1000000000
999999999 1000000000 2 1000000000
出力例 3
5000000000
- 答えは非常に大きくなりうることに注意してください