提出 #73776573

---

ソースコード 拡げる

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> P(N);
    for (int i = 0; i < N; i++) cin >> P[i];
    int S, T;
    cin >> S >> T;
    S--; T--;

    const ll INF = 1e18;
    vector<vector<ll>> dist(N, vector<ll>(N, INF));
    for (int i = 0; i < N; i++) dist[i][i] = 0;

    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        dist[u][v] = w;
        dist[v][u] = w;
    }

    // Floyd–Warshall
    for (int k = 0; k < N; k++)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    int fullMask = 1 << N;
    vector<vector<ll>> dp(fullMask, vector<ll>(N, -INF));

    dp[1 << S][S] = P[S];

    for (int mask = 0; mask < fullMask; mask++) {
        for (int last = 0; last < N; last++) {
            if (dp[mask][last] < -INF/2) continue;
            for (int nxt = 0; nxt < N; nxt++) {
                if (mask >> nxt & 1) continue; // already visited
                if (dist[last][nxt] >= INF) continue; // unreachable
                int newMask = mask | (1 << nxt);
                ll newProfit = dp[mask][last] + P[nxt] - dist[last][nxt];
                if (newProfit > dp[newMask][nxt]) {
                    dp[newMask][nxt] = newProfit;
                }
            }
        }
    }

    ll ans = -INF;
    for (int mask = 0; mask < fullMask; mask++) {
        if (mask >> T & 1) {
            ans = max(ans, dp[mask][T]);
        }
    }

    cout << ans << endl;

    return 0;
}

提出情報

ジャッジ結果