概要

各倉庫の在庫に対して、複数の「出る量」「入る量」を一括で反映し、最終在庫が最大となる倉庫番号（同率なら最小番号）を求めます。

考察

配送指示は逐次処理ではなく「一括反映」なので、順番は関係ありません。倉庫 \(i\) の最終在庫は

• 初期在庫 \(P_i\)
• 入ってくる総量（他倉庫から \(i\) へ）
• 出ていく総量（\(i\) から他倉庫へ）

をまとめて計算すればよく、最終的に
\(P_i + (\text{入る総量}) - (\text{出る総量})\) になります。

素朴に「各指示ごとに全倉庫の状態を逐次更新する」こと自体は \(M\) 回の更新で済むので一見 \(O(M)\) ですが、問題の本質は「入出を集計してから最終値を出す」だけで十分、という点です。特に、同じ倉庫に対して多数の指示があるときも、各倉庫の増減分を合計して持っておけば、最後に一度だけ最終在庫を計算できます。

ここで有効なのが「差分（増減）配列」です。各倉庫 \(i\) について増減分 \(\Delta_i\) を用意し、

• \(u \to v\) に \(w\) 移動なら、\(u\) は \(w\) 減るので \(\Delta_u -= w\)
• \(v\) は \(w\) 増えるので \(\Delta_v += w\)

と足し合わせていきます。最後に \(P_i + \Delta_i\) を見て最大を探せば答えです。

（例）\(P=[10,5,7]\)、指示「\(1\to2\) に \(3\)」「\(3\to2\) に \(2\)」
\(\Delta=[-3, +5, -2]\) なので最終は \([7,10,5]\)、最大は倉庫2。

アルゴリズム

1. 長さ \(N\) の配列 delta を \(0\) で初期化する（各倉庫の増減分）。
2. 各配送指示 \((U, V, W)\) について
   • delta[U] -= W
   • delta[V] += W を行う（添字は 0-index に直す）。
3. 各倉庫 \(i\) の最終在庫 P[i] + delta[i] を計算し、最大値を更新する。
4. 最大在庫の倉庫が複数ある場合は最小番号が必要だが、左から順に「> のときだけ更新」すれば自然に最小番号が残る。
5. 1-index に戻して出力する。

計算量

• 時間計算量: \(O(N + M)\)（配送指示の集計 \(M\) 回＋最大探索 \(N\) 回）
• 空間計算量: \(O(N)\)（差分配列 delta）

実装のポイント

• 増減量や最終在庫は最大で \(10^9\) が多数回足し引きされるため、言語によっては 64bit 整数が必要です（Python は自動で多倍長なので安心）。

• 入力サイズが大きいので、Python では sys.stdin.buffer.readline を使うと高速です。

• 同率のとき最小番号を選ぶため、比較は >= ではなく > を使って「最初に見つかった最大」を保持します。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    delta = [0] * N

    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        delta[u] -= w
        delta[v] += w

    max_val = -10**30
    ans = 0
    for i in range(N):
        val = P[i] + delta[i]
        if val > max_val:
            max_val = val
            ans = i

    print(ans + 1)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。