oj.uz

Submission #1012694

# Submission time Handle Problem Language Result Execution time Memory
1012694 2024-07-02T13:51:11 Z hengliao Cities (BOI16_cities) C++17
14 / 100
 378 ms 39668 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12892 KB Output is correct
2 Correct 6 ms 12892 KB Output is correct
3 Correct 7 ms 12892 KB Output is correct
4 Incorrect 5 ms 12768 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 34148 KB Output is correct
2 Correct 251 ms 33604 KB Output is correct
3 Correct 66 ms 20308 KB Output is correct
4 Correct 231 ms 39668 KB Output is correct
5 Correct 144 ms 31692 KB Output is correct
6 Correct 111 ms 33468 KB Output is correct
7 Correct 7 ms 13148 KB Output is correct
8 Correct 6 ms 13148 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 13148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 378 ms 34192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 19540 KB Output isn't correct
2 Halted 0 ms 0 KB -