제출 #1245784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245784		phuonglinhn09	Cities (BOI16_cities)	C++20	100 / 100	1947 ms	50916 KiB

cities

/**
 *   author:   phuonglinhn09
 *   created:  23.07.2025
 */

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int nmax = 1e5;
const ll inf = 1e18;

ll n, k, m, dp[nmax + 5][40];
vector<pair<int, ll>> adj[nmax + 5];

namespace SOLVE{
    void solve() {
        for (int mask = 1; mask < (1 << k); mask++) {
            priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;

            for (int i = 1; i <= n; i++) {
                for (int sub = mask; sub > 0; sub = (sub - 1) & mask){
                    dp[i][mask] = min(dp[i][mask], dp[i][sub] + dp[i][mask ^ sub]);
                }
                if (dp[i][mask] < inf) pq.emplace(dp[i][mask],i);
            }

            while (!pq.empty()) {
                auto [cur, u] = pq.top(); pq.pop();
                if (cur > dp[u][mask]) continue;
                for (auto [v,w]:adj[u]) {
                    if (dp[v][mask] > cur + w){
                        dp[v][mask] = cur + w;
                        pq.emplace(dp[v][mask],v);
                    }
                }
            }
        }
        ll ans = inf;
        for (int u = 1; u <= n; u++) ans = min(ans, dp[u][(1 << k) - 1]);
        cout << ans;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> k >> m;

    memset(dp, 0x3f, sizeof dp);
    for (int i = 0; i < k; i++) {
        int u; cin >> u;
        dp[u][1 << i] = 0;
    }
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    SOLVE::solve();

    return 0;
}

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