Submission #1343436

#TimeUsernameProblemLanguageResultExecution timeMemory
1343436nguyenkhangninh99Relay Marathon (NOI20_relaymarathon)C++20
100 / 100
1674 ms364888 KiB
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
vector<pair<int, int>> g[maxn];
map<int, int> d[maxn];
int spec[maxn];

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

    int n, m, k; cin >> n >> m >> k;
    for(int i = 1; i <= m; i++){
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
    for(int i = 1; i <= k; i++){
        int x; cin >> x;
        pq.push({0, x, x});
        spec[x] = 1;
        d[x][x] = 0;
    }
    vector<array<int, 3>> banhhe;
    int ans = 1e18;
    while(pq.size()){
        auto [dist, root, u] = pq.top();
        pq.pop();
        if(dist != d[root][u]) continue;
        if(dist >= ans) break;
        if(u != root && spec[u]){
            for(int i = 0; i < banhhe.size(); i++){
                auto [dist2, x, y] = banhhe[i];
                if(x != root && x != u && y != root && y != u) ans = min(ans, dist2 + dist);
            }
            banhhe.push_back({dist, root, u});
        }

        for(auto [v, w]: g[u]){
            if(d[root].find(v) != d[root].end() && d[root][v] <= dist + w) continue;
            d[root][v] = dist + w;
            pq.push({dist + w, root, v});
        }
    }

    cout << ans;
    return 0;
}




Compilation message (stderr)

RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:27:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 |     int ans = 1e18;
      |               ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...