D - トレジャーハント 解説 /

実行時間制限: 3 sec / メモリ制限: 256 MB

問題文

高橋君が住む国には N 箇所の町と町同士をつなぐ一方通行の道が M 本あり、それぞれの町には 1 から N の番号が割りふられています。 i 番目の道は a_i 番の町から b_i 番の町へ移動することが可能であり、移動に c_i 分だけかかります。

所持金が 0 円の高橋君は T 分間のトレジャーハントに出かけることにしました。高橋君は開始 0 分の時点で 1 番の町にいます。また、開始から T 分の時点にも 1 番の町にいなくてはなりません。高橋君が i 番の町に 1 分間滞在すると、 A_i 円が高橋君の所持金に加算されます。

T 分間のトレジャーハントによって高橋君の所持金は最大いくらになるか求めてください。

入力

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

N M T
A_1 … A_N
a_1 b_1 c_1
.
.
.
a_M b_M c_M
  • 1 行目に町の数と道の数、トレジャーハントの分数を表す 3 つの整数 N,M,T (2≦N≦10^5, 1≦M≦min(N(N-1),10^5), 1≦T≦10^9) が空白区切りで与えられる。
  • 2 行目には i 番目の町に滞在したときに得られるお金の情報を表す整数 A_i(1≦A_i≦10^5) が空白区切りで与えられる。
  • 3 行目から続く M 行のうち i 行目においては、 i 番目の道の情報を表す 3 つの整数 a_i, b_i, c_i (1≦a_i,b_i≦N,a_i≠b_i, 1≦c_i≦10^5)が空白区切りで与えられる。
  • i≠j であるような i,j において、a_i≠a_j または b_i≠b_j のどちらかが成立する。

出力

トレジャーハントの結果としてありうる高橋君の所持金のうち最大値を 1 行に出力せよ。改行を忘れないこと。

部分点

この問題には部分点が設定されている。

  • 1≦N≦200 を満たすデータセットに正解した場合 50 点が与えられる。
  • 追加制約のないデータセットに正解した場合は、追加で 50 点が与えられ、合計 100 点が得られる。

入力例 1

2 2 5
1 3
1 2 2
2 1 1

出力例 1

6
  • 開始から 0 分の時点から 2 分かけて町 1 から町 2 に移動します。
  • 開始から 2 分の時点から 2 分間、町 2 に滞在します。所持金は 6 円になります。
  • 開始から 4 分の時点から 1 分かけて町 2 から町 1 に移動します。
  • 開始から 5 分の時点で町 1 にいます。トレジャーハントが終了します。
  • このケースは部分点の制約を満たします。

入力例 2

2 2 3
1 3
1 2 2
2 1 1

出力例 2

3
  • 開始 0 分の時点から 3 分間、町 1 に滞在するのが最適であり、所持金を 3 円にすることができます。
  • このケースは部分点の制約を満たします。

入力例 3

8 15 120
1 2 6 16 1 3 11 9
1 8 1
7 3 14
8 2 13
3 5 4
5 7 5
6 4 1
6 8 17
7 8 5
1 4 2
4 7 1
6 1 3
3 1 10
2 6 5
2 4 12
5 1 30

出力例 3

1488
  • このケースは部分点の制約を満たします。