제출 #1012784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1012784		hengliao	Cities (BOI16_cities)	C++17	100 / 100	2782 ms	49844 KiB

cities

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

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

const ll mxN=2e5+5;
const ll inf=1e18;

ll n, m, k;

vector<pll> adj[mxN];
vector<pair<ll, pll>> edges;
ll dis[mxN][5];
ll con[5];
ll dsu[21];
ll dis2[mxN];
ll dis3[mxN];

ll find_set(ll a){
    if(dsu[a]<0) return a;
    return dsu[a]=find_set(dsu[a]);
}

void unite(ll a, ll b){
    ll f=find_set(a);
    ll s=find_set(b);
    if(abs(dsu[f])<abs(dsu[s])){
        swap(f, s);
    }
    dsu[f]+=dsu[s];
    dsu[s]=f;
}

bool visited[mxN];

void solve(){
	cin>>n>>k>>m;
    for(ll i=0;i<k;i++){
        cin>>con[i];
    }
    for(ll i=0;i<m;i++){
        ll u, v, w;
        cin>>u>>v>>w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
        edges.pb({w, {u, v}});
    }
    sort(edges.begin(), edges.end());
    if(n<=20){
        ll ans=inf;
        for(ll mask=0;mask<(1LL<<n);mask++){
            bool good=1;
            for(ll i=0;i<k;i++){
                if((mask&(1LL<<(con[i]-1)))==0){
                    good=0;
                }
            }
            memset(dsu, -1, sizeof(dsu));
            ll cur=0;
            for(auto &edge:edges){
                ll w=edge.F;
                ll u=edge.S.F;
                ll v=edge.S.S;
                if((mask&(1LL<<(u-1)))==0 || (mask&(1LL<<(v-1)))==0){
                    continue;
                }
                if(find_set(u)!=find_set(v)){
                    cur+=w;
                    unite(u, v);
                }
            }
            for(ll i=1;i<k;i++){
                if(find_set(con[0])!=find_set(con[i])){
                    good=0;
                }
            }
            if(good) ans=min(ans, cur);
        }
        cout<<ans<<'\n';
        return;
    }
    if(k==2){
        //memset(visited, 0, sizeof(visited));
        memset(dis, -1, sizeof(dis));
        priority_queue<pll, vector<pll>, greater<pll>> pq;
        pq.push({0, con[0]});
        while(!pq.empty()){
            pll cur=pq.top(); pq.pop();
            if(dis[cur.S][0]!=-1) continue;
            dis[cur.S][0]=cur.F;
            for(auto &[x, y]:adj[cur.S]){
                pq.push({cur.F+y, x});
            }
        }
        cout<<dis[con[1]][0]<<'\n';
        return;
    }
    else if(k==3){
        memset(dis, -1, sizeof(dis));
        for(ll i=0;i<3;i++){
            priority_queue<pll, vector<pll>, greater<pll>> pq;
            pq.push({0, con[i]});
            while(!pq.empty()){
                pll cur=pq.top(); pq.pop();
                if(dis[cur.S][i]!=-1) continue;
                dis[cur.S][i]=cur.F;
                for(auto &[x, y]:adj[cur.S]){
                    pq.push({cur.F+y, x});
                }
            }
        }
        ll ans=inf;
        for(ll i=1;i<=n;i++){
            ans=min(ans, dis[i][0]+dis[i][1]+dis[i][2]);
        }
        cout<<ans<<'\n';
        return;
    }
    else if(k==4){
        memset(dis, -1, sizeof(dis));
        for(ll i=0;i<4;i++){
            priority_queue<pll, vector<pll>, greater<pll>> pq;
            pq.push({0, con[i]});
            while(!pq.empty()){
                pll cur=pq.top(); pq.pop();
                if(dis[cur.S][i]!=-1) continue;
                dis[cur.S][i]=cur.F;
                for(auto &[x, y]:adj[cur.S]){
                    pq.push({cur.F+y, x});
                }
            }
        }
        ll ans=inf;
        for(ll i=1;i<=n;i++){
            /*cout<<i<<' '<<dis[i][0]+dis[i][1]+dis[i][2]+dis[i][3]<<'\n';
            for(ll j=0;j<4;j++){
                cout<<dis[i][j]<<' ';
            }
            cout<<'\n';*/
            ans=min(ans, dis[i][0]+dis[i][1]+dis[i][2]+dis[i][3]);
        }
        //cout<<ans<<'\n';
        for(ll ex=0;ex<4;ex++){
            ll mn=inf;
            for(ll i=0;i<4;i++){
                if(i==ex){
                    continue;
                }
                mn=min(mn, dis[con[i]][ex]);
            }
            for(ll mid=1;mid<=n;mid++){
                ll tep=0;
                for(ll i=0;i<4;i++){
                    if(i==ex) continue;
                    tep+=dis[mid][i];
                }
                tep+=mn;
                ans=min(ans, tep);
            }
        }
        /*memset(tepdis, -1, sizeof(tepdis));
        for(ll i=1;i<=n;i++){
            priority_queue<pll, vector<pll>, greater<pll>> pq;
            pq.push({0, i});
            while(!pq.empty()){
                pll cur=pq.top(); pq.pop();
                if(tepdis[cur.S][i]!=-1) continue;
                tepdis[cur.S][i]=cur.F;
                for(auto &[x, y]:adj[cur.S]){
                    pq.push({cur.F+y, x});
                }
            }
        }*/
        for(ll i=1;i<4;i++){
            memset(dis2, -1, sizeof(dis2));
            priority_queue<pll, vector<pll>, greater<pll>> pq;
            priority_queue<pll, vector<pll>, greater<pll>> pq2;
            for(ll j=1;j<=n;j++){
                pq.push({dis[j][0]+dis[j][i], j});
            }
            while(!(pq.empty() && pq2.empty())){
                pll cur1={inf, inf};
                pll cur2={inf, inf};
                if(!pq.empty()){
                    cur1=pq.top();
                }
                if(!pq2.empty()){
                    cur2=pq2.top();
                }
                pll cur;
                if(cur1.F<cur2.F){
                    pq.pop();
                    cur.F=cur1.F;
                    cur.S=cur1.S;
                }
                else{
                    pq2.pop();
                    cur.F=cur2.F;
                    cur.S=cur2.S;
                }
                if(dis2[cur.S]!=-1) continue;
                dis2[cur.S]=cur.F;
                for(auto &[x, y]:adj[cur.S]){
                    pq2.push({cur.F+y, x});
                }
            }
            for(ll mid=1;mid<=n;mid++){
                ll tep=dis2[mid];
                for(ll j=1;j<4;j++){
                    if(j==i) continue;
                    tep+=dis[mid][j];
                }
                ans=min(ans, tep);
            }
        }
        cout<<ans<<'\n';
        return;
    }
    else{
        memset(dis, -1, sizeof(dis));
        for(ll i=0;i<5;i++){
            priority_queue<pll, vector<pll>, greater<pll>> pq;
            pq.push({0, con[i]});
            while(!pq.empty()){
                pll cur=pq.top(); pq.pop();
                if(dis[cur.S][i]!=-1) continue;
                dis[cur.S][i]=cur.F;
                for(auto &[x, y]:adj[cur.S]){
                    pq.push({cur.F+y, x});
                }
            }
        }
        ll ans=inf;
        for(ll i=1;i<=n;i++){
            /*cout<<i<<' '<<dis[i][0]+dis[i][1]+dis[i][2]+dis[i][3]<<'\n';
            for(ll j=0;j<4;j++){
                cout<<dis[i][j]<<' ';
            }
            cout<<'\n';*/
            ans=min(ans, dis[i][0]+dis[i][1]+dis[i][2]+dis[i][3]+dis[i][4]);
        }
        //cout<<ans<<'\n';
        /*memset(tepdis, -1, sizeof(tepdis));
        for(ll i=1;i<=n;i++){
            priority_queue<pll, vector<pll>, greater<pll>> pq;
            pq.push({0, i});
            while(!pq.empty()){
                pll cur=pq.top(); pq.pop();
                if(tepdis[cur.S][i]!=-1) continue;
                tepdis[cur.S][i]=cur.F;
                for(auto &[x, y]:adj[cur.S]){
                    pq.push({cur.F+y, x});
                }
            }
        }*/
        for(ll i=2;i<5;i++){
            memset(dis2, -1, sizeof(dis2));
            priority_queue<pll, vector<pll>, greater<pll>> pq;
            priority_queue<pll, vector<pll>, greater<pll>> pq2;
            for(ll j=1;j<=n;j++){
                pq.push({dis[j][1]+dis[j][i], j});
            }
            while(!(pq.empty() && pq2.empty())){
                pll cur1={inf, inf};
                pll cur2={inf, inf};
                if(!pq.empty()){
                    cur1=pq.top();
                }
                if(!pq2.empty()){
                    cur2=pq2.top();
                }
                pll cur;
                if(cur1.F<cur2.F){
                    pq.pop();
                    cur.F=cur1.F;
                    cur.S=cur1.S;
                }
                else{
                    pq2.pop();
                    cur.F=cur2.F;
                    cur.S=cur2.S;
                }
                if(dis2[cur.S]!=-1) continue;
                dis2[cur.S]=cur.F;
                for(auto &[x, y]:adj[cur.S]){
                    pq2.push({cur.F+y, x});
                }
            }
            memset(dis3, -1, sizeof(dis3));
            for(ll j=1;j<=n;j++){
                ll tep=0;
                for(ll k=2;k<5;k++){
                    if(i==k) continue;
                    tep+=dis[j][k];
                }
                pq.push({tep, j});
            }
            while(!(pq.empty() && pq2.empty())){
                pll cur1={inf, inf};
                pll cur2={inf, inf};
                if(!pq.empty()){
                    cur1=pq.top();
                }
                if(!pq2.empty()){
                    cur2=pq2.top();
                }
                pll cur;
                if(cur1.F<cur2.F){
                    pq.pop();
                    cur.F=cur1.F;
                    cur.S=cur1.S;
                }
                else{
                    pq2.pop();
                    cur.F=cur2.F;
                    cur.S=cur2.S;
                }
                if(dis3[cur.S]!=-1) continue;
                dis3[cur.S]=cur.F;
                for(auto &[x, y]:adj[cur.S]){
                    pq2.push({cur.F+y, x});
                }
            }
            for(ll j=1;j<=n;j++){
                ans=min(ans, dis2[j]+dis3[j]+dis[j][0]);
            }
        }
        for(ll s=1;s<5;s++){
            for(ll i=1;i<5;i++){
                if(i==s) continue;
                memset(dis2, -1, sizeof(dis2));
                priority_queue<pll, vector<pll>, greater<pll>> pq;
                priority_queue<pll, vector<pll>, greater<pll>> pq2;
                for(ll j=1;j<=n;j++){
                    pq.push({dis[j][0]+dis[j][i], j});
                }
                while(!(pq.empty() && pq2.empty())){
                    pll cur1={inf, inf};
                    pll cur2={inf, inf};
                    if(!pq.empty()){
                        cur1=pq.top();
                    }
                    if(!pq2.empty()){
                        cur2=pq2.top();
                    }
                    pll cur;
                    if(cur1.F<cur2.F){
                        pq.pop();
                        cur.F=cur1.F;
                        cur.S=cur1.S;
                    }
                    else{
                        pq2.pop();
                        cur.F=cur2.F;
                        cur.S=cur2.S;
                    }
                    if(dis2[cur.S]!=-1) continue;
                    dis2[cur.S]=cur.F;
                    for(auto &[x, y]:adj[cur.S]){
                        pq2.push({cur.F+y, x});
                    }
                }
                memset(dis3, -1, sizeof(dis3));
                for(ll j=1;j<=n;j++){
                    ll tep=0;
                    for(ll k=1;k<5;k++){
                        if(k==i || k==s) continue;
                        tep+=dis[j][k];
                    }
                    pq.push({tep, j});
                }
                while(!(pq.empty() && pq2.empty())){
                    pll cur1={inf, inf};
                    pll cur2={inf, inf};
                    if(!pq.empty()){
                        cur1=pq.top();
                    }
                    if(!pq2.empty()){
                        cur2=pq2.top();
                    }
                    pll cur;
                    if(cur1.F<cur2.F){
                        pq.pop();
                        cur.F=cur1.F;
                        cur.S=cur1.S;
                    }
                    else{
                        pq2.pop();
                        cur.F=cur2.F;
                        cur.S=cur2.S;
                    }
                    if(dis3[cur.S]!=-1) continue;
                    dis3[cur.S]=cur.F;
                    for(auto &[x, y]:adj[cur.S]){
                        pq2.push({cur.F+y, x});
                    }
                }
                for(ll j=1;j<=n;j++){
                    ans=min(ans, dis2[j]+dis3[j]+dis[j][s]);
                }
            }
        }
        cout<<ans<<'\n';
        return;
    }

}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	solve();
	return 0;
}

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