Yukicoder030 たこ焼き工場

問題概要

頂点が$N$個,辺が$M$本の閉路のない有向グラフがある。辺に値が定められており、これを端の頂点から頂点$N$まで伝搬していく。最終的に頂点$N$の値は何になるか。

$N\leqq10^2$、$M\leqq1.5*10^3$

yukicoder030

解法

入次数がゼロのとこから再帰すると、頂点$N$を末尾にしたボトムアップな計算にできるので、これはメモ化再帰でできる。
最初、グラフを反転させてdfsをしてTLEしてしまった。

計算量:$O(N^3)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using PII = pair<int, int>;   using PLL = pair<LL, LL>;
    using VL = vector<LL>;        using VVL = vector<VL>;
    #define SZ(a) int((a).size())
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    
    LL N, M;
    LL ans = 0LL;
    
    LL dfs(int v, VL& need, vector<vector<PII>>& G) {
        if (need[v] != 0) {
            return need[v];
        }
        LL res = 0;
        FOR(i, 0, SZ(G[v])) {
            res += dfs(G[v][i].first, need, G)*G[v][i].second;
        }
    
        return need[v] = res;
    }
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N >> M;
        vector<vector<PII>> G(N), rG(N);
        FOR(i, 0, M) {
            int a, b, c; cin >> a >> b >> c;
            a--; c--;
            rG[c].push_back(PII(a, b));
            G[a].push_back(PII(c, b));
        }
    
        vector<LL> need(N, 0);
        need[N - 1] = 1;
        FOR(i, 0, N - 1) {
            if (SZ(rG[i])) {
                cout << 0 << endl;
            }
            else cout << dfs(i, need, G) << endl;
        }
    
        return 0;
    }