제출 #1315110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315110		huypham2009	Cities (BOI16_cities)	C++20	59 / 100	904 ms	36944 KiB

cities

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

const long long INF = (long long)1e18;
const int MAXK = 5;

int n, m, k;
int imp[MAXK];
vector<pair<int,int>> g[100005];
long long dp[1 << MAXK][100005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k >> m;
    for (int i = 0; i < k; i++) cin >> imp[i];

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    int FULL = 1 << k;
    for (int mask = 0; mask < FULL; mask++)
        for (int i = 1; i <= n; i++)
            dp[mask][i] = INF;

    for (int i = 0; i < k; i++) {
        int mask = 1 << i;
        dp[mask][imp[i]] = 0;

        priority_queue<pair<long long,int>,
            vector<pair<long long,int>>,
            greater<pair<long long,int>>> pq;

        pq.push({0, imp[i]});
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d != dp[mask][u]) continue;
            for (auto [v, w] : g[u]) {
                if (dp[mask][v] > d + w) {
                    dp[mask][v] = d + w;
                    pq.push({dp[mask][v], v});
                }
            }
        }
    }

    for (int mask = 1; mask < FULL; mask++) {
        long long hi = INF;

        for (int sub = (mask - 1) & mask; sub; sub = (sub - 1) & mask) {
            int other = mask ^ sub;
            if (sub < other) break;
            for (int u = 1; u <= n; u++) {
                if (dp[sub][u] == INF || dp[other][u] == INF) continue;
                dp[mask][u] = min(dp[mask][u], dp[sub][u] + dp[other][u]);
            }
        }

        for (int u = 1; u <= n; u++)
            hi = min(hi, dp[mask][u]);

        if (hi == INF) continue;

        priority_queue<pair<long long,int>,
            vector<pair<long long,int>>,
            greater<pair<long long,int>>> pq;

        for (int u = 1; u <= n; u++) {
            if (dp[mask][u] != INF && dp[mask][u] - hi <= 10000) {
                pq.push({dp[mask][u], u});
            }
        }

        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d != dp[mask][u]) continue;
            for (auto [v, w] : g[u]) {
                if (dp[mask][v] > d + w) {
                    dp[mask][v] = d + w;
                    pq.push({dp[mask][v], v});
                }
            }
        }
    }

    long long ans = INF;
    for (int i = 1; i <= n; i++)
        ans = min(ans, dp[FULL - 1][i]);

    cout << ans;
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 23 / 23
• Subtask 5: 0 / 26