제출 #495132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
495132		Nalrimet	Evacuation plan (IZhO18_plan)	C++17	54 / 100	457 ms	19264 KiB

plan

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int inf = 1000000000;

#define F first
#define S second
#define pb push_back

vector<pair<int, int>> g[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
priority_queue<pair<int, int>> q1;
int n, m, d[N], p[N], k, qq;
bool used[N];

int ans(int s, int t){
    int res = min(d[s], d[t]);
    q1.push({d[s], s});
    while(!q1.empty()){
        if(used[t]) break;
        int v = q1.top().S;
        int d_v = q1.top().F;
//        cout << v << ' ' << d_v << '\n';
        q1.pop();
        res = min(res, d_v);
        for(auto edge : g[v]){
            int to = edge.F;
            if(!used[to]){
                q1.push({d[to], to});
                used[to] = 1;
            }
        }
    }
    while(!q1.empty()){
        q1.pop();
    }
    for(int i = 1; i <= n; ++i){
        used[i] = 0;
    }
    return res;
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    for(int i = 1, a, b, w; i <= m; ++i){
        cin >> a >> b >> w;
        g[a].pb({b, w});
        g[b].pb({a, w});
    }

    for(int i = 1; i <= n; ++i){
        d[i] = inf;
    }

    cin >> k;

    for(int i = 1, x; i <= k; ++i){
        cin >> x;
        d[x] = 0;
        q.push({0, x});
    }

    while(!q.empty()){
        int v = q.top().S;
        int d_v = q.top().F;
        q.pop();
        if(d_v != d[v]) continue;
        for(auto edge : g[v]){
            int to = edge.F;
            int len = edge.S;
            if(d[v] + len < d[to]){
                d[to] = d[v] + len;
                q.push({d[to], to});
            }
        }
    }

//    for(int i = 1; i <= n; ++i){
//        cout << d[i] << ' ';
//    }

    cin >> qq;

    if(qq == 1 || (qq <= 200 && n <= 15 && m <= 200)){
        while(qq--){
            int s, t;
            cin >> s >> t;
            cout << ans(s, t) << '\n';
        }
    }
    else{
        while(qq--){
            int s, t;
            cin >> s >> t;
            cout << min(d[s], d[t]) << '\n';
        }
    }

    return 0;

}

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