oj.uz

Submission #640788

# Submission time Handle Problem Language Result Execution time Memory
640788 2022-09-15T09:08:18 Z KindaNameless Cities (BOI16_cities) C++14
0 / 100
 355 ms 17032 KB 
#include<algorithm>
#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){
        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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Incorrect 1 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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