Submission #1271527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271527		rayan_bd	Cities (BOI16_cities)	C++20	0 / 100	177 ms	18876 KiB

cities

#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5 + 100;
#define int long long
const int inf = 1e18;
vector<pair<int, int>> adj[mxN];
map<int, vector<int>> mp;
int mark[mxN];
void djikstra(int u, int n){
    vector<int> dist(n + 1, inf);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[u] = 0;
    pq.push({0, u});
    while(pq.size()){
        auto tp = pq.top();
        pq.pop();
        if(dist[tp.second] < tp.first) continue;
        for(auto it : adj[tp.second]){
            if(dist[it.first] > tp.first + it.second){
                dist[it.first] = tp.first + it.second;
                pq.push({dist[it.first], it.first});
            }
        }
    }
    mp[u] = dist;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, k, m, u, v, w;
    cin >> n >> k >> m;
    for(int i = 1; i <= k; ++i){
        cin >> mark[i];
    }
    for(int i = 1; i <= m; ++i){
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for(int i = 1; i <= k; ++i){
        djikstra(mark[i], n);
    }
    assert(k <= 3);
    if(k == 2){
        cout << mp[mark[1]][mark[2]] << "\n";
    }else{
        int ans = inf;
        for(int i = 1; i <= k; ++i){
            int middle = mark[i];
            int a = 0, b = 0;
            if(i == 1) a = mark[2], b = mark[3];
            if(i == 2) a = mark[1], b = mark[3];
            if(i == 3) a = mark[1], b = mark[2];
            ans = min(ans, mp[middle][a] + mp[middle][b]);
        }
        cout << ans << "\n";
    }
    return 0;
}

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