Submission #565746

#TimeUsernameProblemLanguageResultExecution timeMemory
565746birthdaycakeEvacuation plan (IZhO18_plan)C++17
35 / 100
4019 ms51016 KiB
#include<bits/stdc++.h>
#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;
    set<pair<int,int>>d;
    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});
        if(a > b) swap(a,b);
        d.insert({a,b});
    }
    
    int k; cin >> k;
    set<pair<int,int>>bfs;
    
    for(int i = 1; i <= n; i++) npp[i] = INT_MAX;

    
    
    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; cin >> a >> b;
        if(a > b) swap(a,b);
        if(d.count({a,b})){
            cout << min(npp[a],npp[b]) << endl;
        }else{
            for(int i = 1; i <= n; i++) dist[i] = 0;
            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 > dist[s.first]){
                            dist[s.first] = c;
                            bfs.insert({dist[s.first],s.first});
                        }
                }
            }
            cout << dist[b] << endl;
        }
        
            
        
    }
   
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...