제출 #723401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
723401		_martynas	Cities (BOI16_cities)	C++11	100 / 100	1932 ms	70008 KiB

cities

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define PB push_back

using ll = long long;
using pii = pair<int, int>;

const int MXN = 2e5+5;
const ll INF = 1e16;

int n, k, m;
int important[MXN];
vector<pii> adj[MXN];
ll dp[32][MXN];
bool visited[MXN];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    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].PB({b, c}), adj[b].PB({a, c});
    }
    fill((ll*)dp, (ll*)dp+32*MXN, INF);
    for(int i = 0; i < k; i++) dp[1<<i][important[i]] = 0;
    priority_queue<pair<ll, int>> PQ;
    for(int mask = 1; mask < (1<<k); mask++) {
        for(int subset = 0; subset < mask; subset++) {
            if((subset | mask) != mask) continue;
            for(int i = 1; i <= n; i++) dp[mask][i] = min(dp[mask][i], dp[subset][i]+dp[subset^mask][i]);
        }
        memset(visited, 0, sizeof(visited));
        for(int i = 1; i <= n; i++) if(dp[mask][i] < INF) PQ.push({-dp[mask][i], i});
        while(!PQ.empty()) {
            ll cost = -PQ.top().F;
            int i = PQ.top().S;
            PQ.pop();
            if(visited[i]) continue;
            visited[i] = true;
            for(auto e : adj[i]) {
                if(visited[e.F]) continue;
                if(dp[mask][e.F] > cost+e.S) {
                    dp[mask][e.F] = cost+e.S;
                    PQ.push({-dp[mask][e.F], e.F});
                }
            }
        }
    }
    cout << *min_element(dp[(1<<k)-1]+1, dp[(1<<k)-1]+n+1);
    return 0;
}

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