Submission #342771

#	Time	Username	Problem	Language	Result	Execution time	Memory
342771		koketsu	Evacuation plan (IZhO18_plan)	C++14	54 / 100	4066 ms	69596 KiB

plan

#include <bits/stdc++.h>
#define pb push_back
#define LL long long
#define Kultivator ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int LL

using namespace std;

const LL Mxn = 1e6 + 7;
const LL Mod = 1e9 + 7;
const LL Inf = 1e14 + 7;

int N, M;

int d[100002], p[100002];

vector<pair<int, int>> g[100002];

map <pair <int, int>, bool> F;

priority_queue<pair<int, int>> q;

signed main(){
    Kultivator;
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        int A, B, W;
        cin >> A >> B >> W;
        g[A].pb({B, W});
        g[B].pb({A, W});
        F[{min(A, B), max(A, B)}] = true;
    }
    for (int i = 1; i <= N; i++) d[i] = 100000000 + 69;
    int K;
    cin >> K;
    for(int i = 1; i <= K; i++){
        int X;
        cin >> X;
        d[X] = false;
        q.push({0, X});
    }
    while(!q.empty()){
        int v = q.top().second;
        q.pop();
        for(auto to : g[v]){
            if(to.second + d[v] < d[to.first]){
                d[to.first] = to.second + d[v];
                q.push({-d[to.first], to.first});
            }
        }
    }
    int Q;
    cin >> Q;
    while(Q--){
        int s, t;
        cin >> s >> t;
        if (F[{min(s, t), max(s, t)}]) {
			cout << min(d[s], d[t]) << '\n';
			continue;
		}
		for (int i = 1; i <= N; i++) p[i] = -1000000;
		p[s] = d[s];
        q.push({p[s], s});
        while(!q.empty()){
            int v = q.top().second;
            q.pop();
            for(auto to : g[v]){
                if(min(d[to.first], p[v]) > p[to.first]){
                    p[to.first] = min(d[to.first], p[v]);
					q.push({ p[to.first], to.first });
                }
            }
        }
        cout << p[t] << '\n';
    }
}

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