oj.uz

Submission #1012674

# Submission time Handle Problem Language Result Execution time Memory
1012674 2024-07-02T13:38:39 Z hengliao Cities (BOI16_cities) C++17
14 / 100
 276 ms 36128 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;
    }

}

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 3 ms 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Incorrect 1 ms 6748 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 276 ms 29980 KB Output is correct
2 Correct 258 ms 29240 KB Output is correct
3 Correct 64 ms 18008 KB Output is correct
4 Correct 227 ms 36128 KB Output is correct
5 Correct 132 ms 27336 KB Output is correct
6 Correct 102 ms 33472 KB Output is correct
7 Correct 4 ms 13148 KB Output is correct
8 Correct 4 ms 13148 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 63 ms 17136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

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