제출 #683030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683030		bebra	Cities (BOI16_cities)	C++17	74 / 100	6102 ms	173676 KiB

cities

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

#define dbg(x) cerr << #x << ": " << x << endl;


const int MAX_N = 1e5 + 5;
const int MAX_M = 2e5 + 5;
const int MAX_K = 5;
const ll INF = 1e18;
vector<pair<int, int>> g[MAX_N];
int vertices[MAX_K];
ll dist[MAX_K][MAX_N];
bool used[MAX_K][MAX_N];
ll dp[MAX_N][1 << MAX_K];
bool used_dp[MAX_N][1 << MAX_K];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, m;
    cin >> n >> k >> m;
    for (int i = 0; i < k; ++i) {
        cin >> vertices[i];
        --vertices[i];
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        int w;
        cin >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    for (int i = 0; i < k; ++i) {
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
        pq.emplace(0, vertices[i]);
        fill_n(dist[i], n, INF);
        dist[i][vertices[i]] = 0;
        while (!pq.empty()) {
            auto [curr_dist, v] = pq.top();
            pq.pop();
            used[i][v] = true;
            for (const auto& [u, w] : g[v]) {
                if (used[i][u]) continue;
                if (curr_dist + w >= dist[i][u]) continue;
                dist[i][u] = curr_dist + w;
                pq.emplace(dist[i][u], u);
            }
        }
    }
    ll ans = INF;
    const int max_mask = (1 << k) - 1;
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int mask = 0; mask <= max_mask; ++mask) {
                dp[j][mask] = INF;
                used_dp[j][mask] = false;
            }
        }
        priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq;
        for (int mask = 0; mask <= max_mask; ++mask) {
            if (!(mask & (1 << i))) continue;
            dp[vertices[i]][mask] = 0;
            for (int j = 0; j < k; ++j) {
                if (mask & (1 << j)) {
                    dp[vertices[i]][mask] += dist[j][vertices[i]];
                }
            }
            pq.emplace(dp[vertices[i]][mask], vertices[i], mask);
        }
        while (!pq.empty()) {
            auto [curr_value, v, curr_mask] = pq.top();
            if (curr_mask == max_mask) {
                ans = min(ans, curr_value);
            }
            pq.pop();
            if (used_dp[v][curr_mask]) continue;
            used_dp[v][curr_mask] = true;
            for (const auto& [u, w] : g[v]) {
                for (int new_mask = curr_mask; new_mask <= max_mask; new_mask = (new_mask + 1) | curr_mask) {
                    if (used_dp[u][new_mask]) continue;
                    ll curr_cost = w;
                    for (int j = 0; j < k; ++j) {
                        if ((new_mask ^ curr_mask) & (1 << j)) {
                            curr_cost += dist[j][u];
                        }
                    }
                    if (curr_value + curr_cost >= dp[u][new_mask]) continue;
                    dp[u][new_mask] = curr_value + curr_cost;
                    pq.emplace(dp[u][new_mask], u, new_mask);
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

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