ABC 373

Table of Contents

D - Hidden Weights

$u_i \rightarrow v_i$ への辺の重みは $w_i$, $v_i \rightarrow u_i$ への辺を $-w_i$ で張り適当なところを $0$ でスタートして新たに訪問したノードに重みに応じて値をおいていく。 負の重みの辺を追加するのがミソ

struct Edge {
    ll to, weight;
};

void dfs(vector<vector<Edge>>& graph, vll& ans, int now) {
    for (auto [to, w] : graph[now]) {
        if (ans[to] != INF)
            continue;
        ans[to] = ans[now] + w;
        dfs(graph, ans, to);
    }
}

void solve() {
    int N, M;
    cin >> N >> M;

    vll u(M), v(M), w(M);
    rep(i, M) {
        cin >> u[i] >> v[i] >> w[i];
        u[i]--, v[i]--;
    }

    vector<vector<Edge>> graph(N);

    rep(i, M) {
        graph[u[i]].push_back({v[i], w[i]});
        graph[v[i]].push_back({u[i], -w[i]});
    }

    vll ans(N, INF);
    rep(i, N) {
        if (ans[i] == INF) {
            ans[i] = 0;
            dfs(graph, ans, i);
        }
    }
    print(ans);
}