oj.uz

Submission #1012673

# Submission time Handle Problem Language Result Execution time Memory
1012673 2024-07-02T13:36:46 Z hengliao Cities (BOI16_cities) C++17
0 / 100
 255 ms 39572 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[2]][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;
    }

}

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 Incorrect 4 ms 12888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 34196 KB Output is correct
2 Correct 252 ms 33644 KB Output is correct
3 Correct 59 ms 20308 KB Output is correct
4 Correct 222 ms 39572 KB Output is correct
5 Incorrect 124 ms 31816 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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