Submission #565717

#	Time	Username	Problem	Language	Result	Execution time	Memory
565717		birthdaycake	Evacuation plan (IZhO18_plan)	C++17	22 / 100	4062 ms	20332 KiB

plan

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);
using namespace std;
 
 
 
vector<pair<int,int>>adj[200001];
int dist[200001],npp[200001];

 



signed main(){
    boost;
    
    int n,m; cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    int k; cin >> k;
    set<pair<int,int>>bfs;
    for(int i = 1; i <= n; i++){
        npp[i] = 1e18;
    }
    for(int i = 1; i <= k; i++) {
        int x; cin >> x;
        npp[x] = 0;
        bfs.insert({0,x});
    }
    
    while(bfs.size()){
        auto x = *bfs.begin();
        bfs.erase(x);
        if(npp[x.second] < x.first) continue;
        for(auto s : adj[x.second]){
            if(npp[x.second] + s.second < npp[s.first]){
                npp[s.first] = npp[x.second] + s.second;
                bfs.insert({npp[s.first], s.first});
            }
        }
    }
    int q; cin >> q;
    while(q--){
        int a,b, ans = 0; cin >> a >> b;
        
        int l = 0, r = 1e9;
        while(l <= r){
            int mid = (l + r) / 2;
            for(int i = 1; i <= n; i++) dist[i] = 0;
            if(npp[a] >= mid) dist[a] = npp[a];
            bfs.insert({dist[a],a});
            while(bfs.size()){
                auto x = *bfs.begin();
                bfs.erase(x);
                if(dist[x.second] > x.first) continue;
                for(auto s : adj[x.second]){
                    int c = min(dist[x.second],npp[s.first]);
                    if(c >= mid){
                        if(c > dist[s.first]){
                            dist[s.first] = c;
                            bfs.insert({dist[s.first],s.first});
                        }
                    }
                }
            }
            if(dist[b] >= mid){
                ans = max(ans,mid);
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        cout << ans << endl;
        
    }
   
    return 0;
}

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