Submission #640792

#	Time	Username	Problem	Language	Result	Execution time	Memory
640792		KindaNameless	Cities (BOI16_cities)	C++14	0 / 100	109 ms	26172 KiB

cities

#include<algorithm>
#include<assert.h>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<numeric>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>
using namespace std;

#define ll long long
#define ld long double

vector<pair<int, ll>> adj[100005];
bool vis[100005], can[100005];
int inc[10], pr[100005];
ll D[100005];
int N, K, M;

void dijkstra(int s){
    for(int i = 1; i <= N; ++i){
        D[i] = 1e16;
        pr[i] = -1;
        vis[i] = 0;
    }

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

    pq.push({0, s});
    D[s] = 0;

    while(!pq.empty()){
        int cur = pq.top().second; ll dist = pq.top().first; pq.pop();

        if(vis[cur])continue;
        vis[cur] = 1;

        for(pair<int, ll> nx : adj[cur]){
            if(D[nx.first] > dist + nx.second){
                D[nx.first] = dist + nx.second;
                pr[nx.first] = cur;
                pq.push({D[nx.first], nx.first});
            }
        }
    }
}

ll solve(int a, int b, int c){
    for(int i = 1; i <= N; ++i){
        can[i] = 0;
    }

    dijkstra(a);

    ll off = D[b], res = 1e16;

    int cur = b;
    while(cur != -1){
        can[cur] = 1;
        cur = pr[cur];
    }

    dijkstra(c);

    for(int i = 1; i <= N; ++i){
        if(can[i])res = min(res, off + D[i]);
    }

    return res;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N >> K >> M;

    for(int i = 1; i <= K; ++i){
        cin >> inc[i];
    }

    for(int i = 1; i <= M; ++i){
        int u, v; ll w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    if(K == 2){
        dijkstra(inc[1]);
        cout << D[inc[2]];
    }
    else if(K == 3){
        assert(0);
        int a = inc[1], b = inc[2], c = inc[3];

        ll ans = 1e16;
        ans = min(ans, solve(a, b, c));
        ans = min(ans, solve(a, c, b));
        ans = min(ans, solve(b, c, a));
        cout << ans;
    }
    else{
        cout << 0;
    }

    return 0;
}

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