Submission #1012694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012694		hengliao	Cities (BOI16_cities)	C++17	14 / 100	378 ms	39668 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];
ll dis[mxN][5];
ll con[5];

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});
    }
    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);
            }
        }
        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: 0 / 22
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26