概要

\(N\) 個のタスクに所要時間と「このタスクが終わらないとあのタスクを始められない」という前提関係が与えられ、全タスクを終える最早時刻（クリティカルパスの長さ）を求める問題です。前提関係に循環がある場合は \(-1\) を出力します。

考察

重要な気づき 1：貪欲に「できるだけ早く始める」のが最適

各タスクの開始時刻 \(S_i\) を遅らせても得はありません。実際、

\[S_i = \max_{(u \to i) \in E} (S_u + A_u)\]

（前提となるタスクが無ければ \(S_i = 0\)）

と、可能な限り早い時刻に設定すれば、すべての制約 \(S_{V_j} \ge S_{U_j} + A_{U_j}\) を満たしつつ、どのタスクの完了時刻 \(S_i + A_i\) も同時に最小化されます。

なぜなら、任意の実行可能解 \(S'\) に対して「\(S_i \le S'_i\) が全 \(i\) で成り立つ」ことが（前提関係の順序に沿った帰納法で）示せるからです。よって答えは

\[\text{answer} = \max_{1 \le i \le N} (S_i + A_i)\]

となります。これは有向グラフ上の最長路（各頂点に重み \(A_i\)）を求めることに相当し、いわゆる PERT / クリティカルパス法です。

重要な気づき 2：循環があると解が存在しない

前提関係を「\(U_j \to V_j\) の有向辺」と見たとき、この有向グラフに閉路があると解は存在しません。例えば \(1 \to 2 \to 1\) なら $\(S_2 \ge S_1 + A_1 > S_1,\quad S_1 \ge S_2 + A_2 > S_2\)\( となり矛盾します（\)A_i \ge 1 > 0\( なので必ず矛盾します）。逆に閉路がなければ（DAG なら）トポロジカル順に上の式で \)S_i$ を決めていけば必ず実行可能解が作れます。

したがって「解が存在しない ⟺ グラフに閉路が存在する」です。

素朴なアプローチの問題点

• 各タスクから再帰的に最長路を計算する：メモ化なしだとパスの数が指数的になり、間に合いません（メモ化すれば下記と同じことになります）。
• 時刻を 1 ずつ進めるシミュレーション：\(A_i \le 10^9\) なので時刻は最大 \(2 \times 10^{14}\) 程度になり得て、到底終わりません。
• 辺の重みを負にして最短路（Bellman-Ford）：\(O(NM)\) で遅く、また閉路検出も必要です。

これらは「グラフがDAGであるならトポロジカル順に一度走査すれば十分」という性質を使うことで \(O(N+M)\) に落ちます。

アルゴリズム

Kahn のアルゴリズム（BFS 型トポロジカルソート）＋DP を用います。

1. 各辺 \(U_j \to V_j\) を隣接リストに追加し、入次数 \(\mathrm{indeg}[V_j]\) を数える。
2. \(S_i\) を全て \(0\) で初期化。
3. \(\mathrm{indeg}[i] = 0\) の頂点をキューに入れる（前提がないタスク＝時刻 \(0\) に開始できるタスク）。
4. キューから頂点 \(u\) を取り出し、処理済みカウンタを \(1\) 増やす。\(u\) の完了時刻 \(f = S_u + A_u\) を計算し、各出辺 \(u \to v\) について
   • \(S_v \leftarrow \max(S_v, f)\)
   • \(\mathrm{indeg}[v]\) を \(1\) 減らし、\(0\) になったら \(v\) をキューに追加。
5. キューが空になったとき、処理済み頂点数が \(N\) 未満なら閉路があるので -1 を出力。
6. そうでなければ \(\max_i (S_i + A_i)\) を出力。

ポイントは、頂点 \(u\) がキューから取り出される時点で \(u\) に入る全ての辺が既に処理済み（\(\mathrm{indeg}[u]\) が \(0\) になっている）なので、\(S_u\) の値が確定しているという点です。

具体例

\(N=4\), \(A = (3, 1, 4, 2)\)、辺が \(1\to2, 1\to3, 2\to4, 3\to4\) の場合：

• \(\mathrm{indeg} = (0,1,1,2)\) なのでキューは \(\{1\}\)。
• \(u=1\)：\(f = 0+3 = 3\)。\(S_2 = 3\), \(S_3 = 3\)、\(\mathrm{indeg}[2],\mathrm{indeg}[3]\) が \(0\) になりキューへ。
• \(u=2\)：\(f = 3+1 = 4\)。\(S_4 = 4\)、\(\mathrm{indeg}[4] = 1\)。
• \(u=3\)：\(f = 3+4 = 7\)。\(S_4 = \max(4,7) = 7\)、\(\mathrm{indeg}[4] = 0\) でキューへ。
• \(u=4\)：\(f = 7+2 = 9\)。

答えは \(\max(3, 4, 7, 9) = 9\)。\(1 \to 3 \to 4\) がクリティカルパスです。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• オーバーフロー：\(A_i \le 10^9\)、パス上に最大 \(N = 2\times10^5\) 個のタスクが並ぶ可能性があるため、完了時刻は最大 \(2\times10^{14}\) 程度になります。32bit 整数では溢れるので、必ず 64bit 整数（long long）を使います。

• キューの実装：std::queue の代わりに vector を用意して添字 idx を進める形にすると、メモリ確保のオーバーヘッドが減って高速です（トポロジカル順の列がそのまま得られるという利点もあります）。

• 隣接リスト：本コードのように head/nxt/to の 3 配列による前方リスト（forward star）方式にすると、vector<vector<int>> より確保が軽く高速です。もちろん vector<vector<int>> でも制約内で十分間に合います。

• 孤立点の扱い：辺のない頂点も \(\mathrm{indeg}=0\) なので自然に初期キューに入り、\(S_i = 0\)、完了時刻 \(A_i\) として答えに反映されます。\(M=0\) のときは答えは \(\max_i A_i\) になります。

• 閉路判定：別途 DFS を書く必要はなく、「トポロジカルソートで取り出せた頂点数が \(N\) に達したか」で判定できます。

• 入力の高速化：\(N\) が \(2\times10^5\) 程度なので、scanf/printf あるいは cin の同期解除（ios::sync_with_stdio(false)）を使うと安心です。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M;
    if(scanf("%d %d", &N, &M)!=2) return 0;
    vector<long long> A(N+1);
    for(int i=1;i<=N;i++){
        long long x; scanf("%lld",&x); A[i]=x;
    }
    vector<int> head(N+1,-1), nxt(M), to(M);
    vector<int> indeg(N+1,0);
    for(int j=0;j<M;j++){
        int u,v; scanf("%d %d",&u,&v);
        to[j]=v; nxt[j]=head[u]; head[u]=j;
        indeg[v]++;
    }
    vector<long long> start(N+1,0);
    vector<int> q; q.reserve(N);
    for(int i=1;i<=N;i++) if(indeg[i]==0) q.push_back(i);
    int cnt=0;
    for(size_t idx=0; idx<q.size(); idx++){
        int u=q[idx]; cnt++;
        long long f = start[u]+A[u];
        for(int e=head[u]; e!=-1; e=nxt[e]){
            int v=to[e];
            if(start[v]<f) start[v]=f;
            if(--indeg[v]==0) q.push_back(v);
        }
    }
    if(cnt!=N){ printf("-1\n"); return 0; }
    long long ans=0;
    for(int i=1;i<=N;i++) ans=max(ans,start[i]+A[i]);
    printf("%lld\n", ans);
    return 0;
}

---

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