Submission #637800

#	Time	Username	Problem	Language	Result	Execution time	Memory
637800		bonk	Evacuation plan (IZhO18_plan)	C++14	54 / 100	4027 ms	28160 KiB

plan

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;
vector<pair<int, int>>adj[N];
bool vis[N];
int danger[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(danger, 0x3f, sizeof(danger));
    int n, m; cin >> n >> m;
    while(m--){
        int u, v, w; cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    int k; cin >> k;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
    for(int i = 0; i < k; i++){
        int x; cin >> x;
        danger[x] = 0;
        pq.emplace(0, x);
    }

    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        for(auto &[v, w]: adj[u]){
            if(danger[v] > d + w){
                danger[v] = d + w;
                pq.emplace(danger[v], v);
            }
        }
    }

    int q; cin >> q;

    while(q--){
        memset(vis, 0, sizeof(vis));
        int a, b; cin >> a >> b;
        bool st2 = false;
        for(auto &[v, w]: adj[a]){
            if(v == b){
                cout << min(danger[a], danger[b]) << '\n';
                st2 = true;
            }
        }

        if(st2) continue;

        priority_queue<pair<int, int>>pq;
        pq.emplace(danger[a], a);
        int ans = min(danger[a], danger[b]);
        bool found = false;

        while(!pq.empty()){
            if(found) break;
            auto [d, u] = pq.top(); pq.pop();
            if(vis[u]) continue;
            vis[u] = true;

            for(auto &[v, w]: adj[u]){
                if(!vis[v]){
                    if(v == b){
                        ans = min(ans, d);
                        found = true;
                        break;
                    }
                    pq.emplace(min(d, danger[v]), v);    
                }
            }
        }

        cout << ans << '\n';
    } 

    return 0;
}

/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1 
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |         auto [d, u] = pq.top(); pq.pop();
      |              ^
plan.cpp:30:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |         for(auto &[v, w]: adj[u]){
      |                   ^
plan.cpp:44:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |         for(auto &[v, w]: adj[a]){
      |                   ^
plan.cpp:60:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |             auto [d, u] = pq.top(); pq.pop();
      |                  ^
plan.cpp:64:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |             for(auto &[v, w]: adj[u]){
      |                       ^

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46