제출 #1282872

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282872		namious	Cities (BOI16_cities)	C++20	100 / 100	2564 ms	44628 KiB

cities

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

#define int long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0) ,cin.tie(0),cout.tie(0);
#pragma GCC optimize("O3,unroll-loops")

const int maxn = 1e5+5 , mod = 1e9+7 , inf = 1e15;

int n, k, m;
vector<pii> adj[maxn];
int important[5];
int dp[maxn][32];

int32_t main() {
    fast_io

    cin >> n >> k >> m;
    for (int i = 0; i < k; i++) {cin >> important[i];}
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    for (int i = 1; i <= n; i++) {
        for (int mask = 0; mask < (1 << k); mask++) {
            dp[i][mask] = inf;
        }
        dp[i][0] = 0;
    }
    for (int i = 0; i < k; i++) {
        int city = important[i];
        dp[city][1 << i] = 0;
    }

    for (int mask = 1; mask < (1 << k); mask++) {
        for (int u = 1; u <= n; u++) {
            for (int mask1 = mask; mask1; mask1 = (mask1 - 1) & mask) {
                int mask2 = mask ^ mask1;
                if (dp[u][mask1] < inf && dp[u][mask2] < inf) {
                    dp[u][mask] = min(dp[u][mask], dp[u][mask1] + dp[u][mask2]);
                }
            }
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (int u = 1; u <= n; u++) {
            if (dp[u][mask] < inf) {
                pq.push({dp[u][mask], u});
            }
        }

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

    int ans = inf;
    for (int u = 1; u <= n; u++) {
        ans = min(ans, dp[u][(1 << k) - 1]);
    }
    cout << ans << endl;

    return 0;
}

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