Submission #637799

#	Time	Username	Problem	Language	Result	Execution time	Memory
637799		bonk	Evacuation plan (IZhO18_plan)	C++14	0 / 100	347 ms	20308 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;
        for(auto &[v, w]: adj[a]){
            if(v == b) cout << min(danger[a], danger[b]) << '\n';
            break;
        }
        
        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;
}

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:43:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |         for(auto &[v, w]: adj[a]){
      |                   ^
plan.cpp:55:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |             auto [d, u] = pq.top(); pq.pop();
      |                  ^
plan.cpp:59:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |             for(auto &[v, w]: adj[u]){
      |                       ^

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