AtCoder Beginner Contest 188E Peddler TLEになってしまう

Question

#AtCoder Beginner Contest 188E Peddler TLEになってしまう
ABC188E
こちらの問題を解いていましたが自分の実装ではTLEになってしまうため、どなたかアドバイスを頂けると幸いです。

問題文

質問内容

非連結のグラフなので0~nでループを回してdfsをしています。
更新済みの場合はskipをしています。

概ねのテストケースは通っていますがいくつかTLEになっています。
O(N+M)の実装だと思っていたのですがTLEになってしまうため、アドバイスをいただきたいです。

実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;

int n, m;
vector<ll> a;
vector<vector<int>> g;
vector<ll> dp;

// 深さ優先探索
void dfs(int v) {
    for(auto nv:g[v]) {
        dp[nv] = min(dp[nv], min(dp[v], a[v]));
        dfs(nv);
    }
}

int main() {
    cin >> n >> m;
    a.resize(n);
    g.resize(n);
    dp.resize(n, INF);
    for(int i=0; i<n; i++) cin >> a[i];
    for(int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
    }

    for(int i=0; i<n; i++) {
        if(dp[i] != INF) continue;
        dfs(i);
    }
    ll res = -INF;
    for(int i=0; i<n; i++) {
        res = max(res, a[i]-dp[i]);
    }
    cout << res << endl;
}

Answer 1

ある町から別のある街に至るルートが複数あり、それらが連結している場合に計算量が爆発します。

5 6
1 1 1 1 1
1 2
1 3
2 3
3 4
3 5
4 5

1から3に至るルートが1→2→3と1→3の2通り、3から5に至るルートが3→4→5と3→5の2通りあります。
これを深さ優先探索すると、3から5に至る2通りのルートが2重に探索されるのが分かるでしょうか。

同様に、5の後ろに2通りのルートを1つ連結するごとに、探索回数が倍々に増えていくことになります。

Comments

[encho]

ありがとうございます。理解できました。
dfsの計算量がO(V+E)となっていますが、一度探索したものはもう通ることはないという前提ですね。

[actorbug]

コメントからすると、dfsで処理済みの道or町をスキップしようとしているように聞こえるのですが、それだとTLEではなくなるもののWAになってしまうと思われます。解説の解法1を実装するであれば、dfsにすること自体が誤りです。

[encho]

そうですね！
ご解説ありがとうございました！