제출 #478495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
478495		Lobo	Cities (BOI16_cities)	C++17	100 / 100	5014 ms	129112 KiB

cities

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

const long long INFll = (long long) 1e16 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 220000

ii n, k, m;
ll dd[6][maxn], d[maxn][50];
vector<pair<ii,ll>> g[maxn];
vector<ii> ci;

void shortp(ii id) {
    for(ii i = 1; i <= n; i++) {
        dd[id][i] = INFll;
    }

    dd[id][ci[id]] = 0;

    priority_queue<pair<ll,ii>> pq; pq.push(mp(0,ci[id]));

    while(pq.size()) {
        ii u = pq.top().sc;
        ll dist = -pq.top().fr;
        pq.pop();

        if(dist != dd[id][u]) continue;

        for(auto V : g[u]) {
            ii v = V.fr;
            ll w = V.sc;

            if(dd[id][u] + w < dd[id][v]) {
                dd[id][v] = dd[id][u] + w;
                pq.push(mp(-dd[id][v],v));
            }
        }
    }
}

void shortp1() {
    priority_queue<pair<ll,pair<ii,ii>>> pq;

    for(ii i = 1; i <= n; i++) {
        for(ii mask = 0; mask < (1<<k); mask++) {
            d[i][mask] = INFll;
        }
        d[i][0] = 0;
        pq.push(mp(0,mp(i,0)));
    }

    while(pq.size()) {
        ii u = pq.top().sc.fr;
        ii mask = pq.top().sc.sc;
        ll dist = -pq.top().fr;
        pq.pop();

        if(dist != d[u][mask]) continue;
    
        for(ii id = 0; id < k; id++) {
            if((mask&(1<<id)) != 0) continue;
            ii mask1 = mask|(1<<id);

            if(d[u][mask1] > d[u][mask] + dd[id][u]) {
                d[u][mask1] = d[u][mask] + dd[id][u];
                pq.push(mp(-d[u][mask1],mp(u,mask1)));
            }
        }

        for(auto V : g[u]) {
            ii v = V.fr;
            ll w = V.sc;

            if(d[v][mask] > d[u][mask] + w) {
                d[v][mask] = d[u][mask] + w;
                pq.push(mp(-d[v][mask],mp(v,mask)));
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    cin >> n >> k >> m;

    for(ii i = 0; i < k; i++) {
        ii x; cin >> x;
        ci.pb(x);
    }

    for(ii i = 0; i < m; i++) {
        ii u, v;
        ll w;
        cin >> u >> v >> w;

        g[u].pb(mp(v,w));
        g[v].pb(mp(u,w));
    }

    for(ii i = 0; i < k; i++) {
        shortp(i);
    }

    shortp1();

    ll ans = INFll;

    for(ii i = 1; i <= n; i++) {
        ans = min(ans, d[i][(1<<k)-1]);
    }

    cout << ans << endl;

}

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