Submission #970148

#	Time	Username	Problem	Language	Result	Execution time	Memory
970148		vjudge1	Evacuation plan (IZhO18_plan)	C++17	0 / 100	120 ms	15464 KiB

plan

#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<pair<int,int>> edges[100001];
ll dist[100001];
bool vis[100001];
ll get(int pos,int target,ll curr) {
    curr = min(dist[pos],curr);
    if (curr == 0) {
        return 0;
    }
    vis[pos] = true;
    if (pos == target) {
        return curr;
    }
    ll maxi = 0;
    for (auto i:edges[pos]) {
        if (!vis[i.second]) {
            maxi = max(maxi,get(i.second,target,curr));
        }
    }
    return maxi;
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    for (int i=1;i<=100000;i++) {
        dist[i] = 1e18;
    }
    int n,m;
    cin >> n >> m;
    int x,y,d;
    for (int i=0;i<m;i++) {
        cin >> x >> y >> d;
        edges[x].push_back({d,y});
        edges[y].push_back({d,x});
    }
    int npp;
    cin >> npp;
    vector<ll> nppn(npp);
    for (int i=0;i<npp;i++) {
        cin >> x;
        nppn[i] = x;
        dist[x] = 0;
    }
    for (auto i:nppn) {
        priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
        pq.push({0,i});
        while (!pq.empty()) {
            auto tmp = pq.top();
            pq.pop();
            if (tmp.first > dist[tmp.second]) {
                continue;
            }
            for (auto j:edges[tmp.second]) {
                if (dist[j.second] > tmp.first+j.first) {
                    dist[j.second] = tmp.first+j.first;
                    pq.push({dist[j.second],j.second});
                }
            }
        }
    }
    int c;
    cin >> c;
    for (int i=0;i<c;i++) {
        for (int j=1;j<=100000;j++) {
            vis[j] = false;
        }
        cin >> x >> y;
        cout << get(x,y,dist[x]) << '\n';
    }
}
/*
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*/

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