제출 #1185567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185567		qwusha	Cities (BOI16_cities)	C++20	100 / 100	4065 ms	51768 KiB

cities

#include <bits/stdc++.h>
using namespace std;
/*
#pragma GCC optimize("O3")
#include <bitset>
#pragma GCC target("avx2")*/
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int inf = 1e15;

int n, k, m;
vector<vector<pair<int,int>>> g;


pair<vector<int>, vector<int>> dijktra(int st) {
    vector<int> dist(n, inf);
    vector<int> par(n, -1);
    dist[st] = 0;
    set<pair<int, int>> q = {{0, st}};
    while(!q.empty()) {
        auto pa = *q.begin();
        q.erase(q.begin());
        int d = pa.fi, v = pa.se;
        for (auto [u, w] : g[v]) {
            if (dist[u] > dist[v] + w) {
                par[u] = v;
                q.erase({dist[u], u});
                dist[u] = dist[v] + w;
                q.insert({dist[u], u});
            }
        }
    }
    return {dist, par};
}



signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k >> m;
    vector<int> a(k);
    g.resize(n);
    for (int i = 0; i < k; i++) {
        cin >> a[i];
        a[i]--;
    }
    for (int i = 0; i < m; i++) {
        int v, u, w;
        cin >> v >> u >> w;
        g[v - 1].push_back({u - 1, w});
        g[u - 1].push_back({v - 1, w});
    }
    vector<vector<int>> di, pars;
    for (auto el: a) {
        auto spa = dijktra(el);
        di.push_back(spa.fi);
        pars.push_back(spa.se);
    }
    int mini = inf;
    vector<vector<int>> dp((1 << k), vector<int>(n, inf));
    for (int i = 0; i < k; i++) {
        int ma = (1 << i);
        for (int j = 0; j < n; j++) {
            dp[ma][j] = di[i][j];
        }
    }
    for (int ma = 0; ma < (1 << k); ma++) {
        for (int cen = 0; cen < n; cen++) {
            for (int subm = 0; subm < (1 << k); subm++) {
                bool ch = 1;
                int m2 = 0;
                for (int i = 0; i < k; i++) {
                    if (((subm >> i) & 1) && !((ma >> i) & 1))
                        ch = 0;
                    else if (!((subm >> i) & 1) && ((ma >> i) & 1)) {
                        m2 = (m2 | (1 << i));
                    }
                }
                if (!ch || (subm == 0 || m2 == 0))
                    continue;
                dp[ma][cen] = min(dp[subm][cen] + dp[m2][cen], dp[ma][cen]);
            }
        }
        set<pair<int, int>> st;
        for (int i = 0; i < n; i++) {
            if (dp[ma][i] != inf) {
                st.insert({dp[ma][i], i});
            }
        }
        while (!st.empty()) {
            auto pa = *st.begin();
            st.erase(pa);
            int v = pa.se, d = pa.fi;
            for (auto [u, w] : g[v]) {
                if (dp[ma][u] > d + w) {
                    st.erase({dp[ma][u], u});
                    dp[ma][u] = d + w;
                    st.insert({dp[ma][u], u});
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        mini = min(mini, dp[dp.size() - 1][i]);
    }
    cout << mini << '\n';
}

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