제출 #485805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
485805		radal	Cities (BOI16_cities)	C++14	22 / 100	1795 ms	16636 KiB

cities

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<ll,int> pll;
typedef pair<long double,long double> pld;
const long long int N = 1e3+10,mod = 998244353,inf = 1e18,maxm = (1 << 24);
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,ll k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
vector<pll> adj[N];
int n,k;
ll d[N][N];
int par[N];
void dij(int v,int i){
    d[v][i] = 0;
    priority_queue<pll> pq;
    pq.push({0,v});
    while (!pq.empty()){
        pll u = pq.top();
        pq.pop();
        if (-u.X != d[u.Y][i]) continue;
        for (pll v : adj[u.Y]){
            if (d[v.X][i] > v.Y+d[u.Y][i]){
                d[v.X][i] = v.Y+d[u.Y][i];
                pq.push({-d[v.X][i],v.X});
            }
        }
    }
}
int getpar(int v){
    if (par[v] == v) return v;
    return par[v] = getpar(par[v]);
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(d,63,sizeof d);
    int m;
    cin >> n >> k >> m;
    vector<int> ve;
    rep(i,0,k){
        int x;
        cin >> x;
        x--;
        ve.pb(x);
    }
    rep(i,0,m){
        int u,v,w;
        cin >> u >> v >> w;
        u--;
        v--;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    rep(i,0,n) dij(i,i);
    int y = (1 << n);
    ll ans = inf;
    rep(j,1,y){
        bool f = 1;
        rep(i,0,k){
            if (!(j&(1 << ve[i]))) f = 0;
        }
        if (!f) continue;
        vector<pair<ll,pll>> e;
        rep(i,0,n){
            par[i] = i;
            if (j&(1 << i))
                rep(x,0,n)
                    if (x != i && j&(1 << x)) e.pb({d[i][x],{i,x}});
                
        }
        sort(e.begin(),e.end());
        ll cost = 0;
        int sz = e.size();
        rep(i,0,sz){
            int u = e[i].Y.X,v = e[i].Y.Y;
            if (getpar(u) != getpar(v)){
                par[par[u]] = par[v];
                cost += e[i].X;
            }
        }
        ans = min(ans,cost);
    }
    cout << ans;
    return 0;
}

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