← 返回题目列表

AtCoder · abc035_d

D. 寻宝

中文机器翻译题面 查看原题

問題文

在高桥君居住的国家, 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
  • 这种情况满足部分点约束。 最好留在