AtCoder ABC 035 D

June 23, 2020

D - トレジャーハント

解説通り、どれかの町にぎりぎりまで滞在して、戻ってきたときの所持金の最大値を求める。滞在する町への行きの最短路は、いつも通りダイクストラ法で求められる。問題は帰りの道の最短路だけれど、これは、最初の町から逆向きに辺をたどって滞在する町へ行きつくときの最短路に一致する。したがって、グラフの辺を逆向きにしたものを持っておけば、行きと同じように帰りの最短路も求められる。

#define MAX_N 100'000
#define INF 1152921504606846976

struct Edge {
    i64 to, cost;
    Edge (i64 to, i64 cost) : to(to), cost(cost) {};
};
vector<Edge> G[MAX_N];
vector<Edge> Gr[MAX_N];

int main() {
    i64 N, M, T; cin >> N >> M >> T;
    vector<i64> A(N);
    REP(i, N) cin >> A[i];

    REP(i, M) {
        i64 u, v, c; cin >> u >> v >> c;
        u--, v--;
        G[u].emplace_back(v, c);
        Gr[v].emplace_back(u, c);
    }

    auto dijkstra = [&](i64 s, bool rev) {
        using P = pair<i64, i64>;
        auto &g = rev ? Gr : G;
        vector<i64> dp(N, INF);
        priority_queue<P, vector<P>, greater<P>> pq;
        dp[s] = 0;
        pq.emplace(0, s);
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();

            if (dp[u] < d) continue;
            for (Edge &e : g[u]) {
                i64 nc = dp[u] + e.cost;
                if (chmin(dp[e.to], nc)) {
                    pq.emplace(nc, e.to);
                }
            }
        }
        return dp;
    };

    vector<i64> d = dijkstra(0, false);
    vector<i64> dr = dijkstra(0, true);

    i64 maxv = 0;
    REP(i, N) {
        i64 rem = T - d[i] - dr[i];
        if (rem < 0) continue;
        chmax(maxv, rem * A[i]);
    }
    cout << maxv << endl;

    return 0;
}