分数: 266 分
问题陈述
高桥在一家公司的物流部门工作。公司拥有 N 仓库,从仓库编号 1 到仓库 N。各仓库 i (1 \leq i \leq N) 目前存储 P_i 项目。
今天, M 已发出在仓库之间移动物品的运输指令。的 j-th (1 \leq j \leq M) 运输指令是“移动 W_j 仓库中的物品 U_j 到仓库 V_j。”在这里, U_j \neq V_j。同一对仓库之间可能存在多个发货指令。
的 M 运输说明是一次性应用的,而不是按顺序应用的。也就是说,每个仓库中的最终物品数量是通过获取初始物品数量,加上进入该仓库的物品总数,并减去该仓库出库的物品总数而获得的。
Takahashi 希望在应用所有发货指令后查找包含最多商品的仓库号。如果有多个仓库,物品最多,则找到仓库编号最小的一个。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 0 \leq P_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq U_j \leq N (1 \leq j \leq M)
- 1 \leq V_j \leq N (1 \leq j \leq M)
- U_j \neq V_j (1 \leq j \leq M)
- 1 \leq W_j \leq 10^9 (1 \leq j \leq M)
- 所有输入值均为整数。
- 保证在应用所有发货指令后,每个仓库中的物品数量为 0 或更多。
输入
N M P_1 P_2 \ldots P_N U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M
- 第一行包含仓库数量 N 和发货说明的数量 M,用空格分隔。
- 第二行包含每个仓库中的初始物品数量 P_1, P_2, \ldots, P_N,用空格分隔。
- 以下 M 行包含每个装运指令的详细信息。如果 M = 0,这部分没有给出。
- 的 j第行 (1 \leq j \leq M) 包含来源仓库编号 U_j,目的仓库号 V_j,以及要移动的项目数 W_j 为 j第一条运输指令,以空格分隔。
输出
应用所有装运指令后,在一行上打印包含最多商品的仓库编号。如果有多个仓库,物品数量最多,则打印数量最少的仓库。
示例输入 1
3 2 10 20 30 1 2 5 3 2 10
示例输出 1
2
示例输入 2
3 2 10 20 10 2 1 5 2 3 5
示例输出 2
1
示例输入 3
6 5 100 200 150 300 250 50 4 2 50 1 3 30 5 6 100 2 1 80 3 5 40
示例输出 3
4
示例输入 4
10 8 500 300 800 200 600 100 450 350 700 250 3 1 200 5 7 150 9 2 300 4 6 100 1 10 400 8 3 50 7 9 100 6 5 50
示例输出 4
3
示例输入 5
1 0 1000000000
示例输出 5
1