Submission #637774

#	Time	Username	Problem	Language	Result	Execution time	Memory
637774		bonk	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4088 ms	29468 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;
        priority_queue<pair<int, int>>pq;
        pq.emplace(danger[a], a);
        int ans = danger[a];

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

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

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