제출 #565771

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

plan

#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];
            priority_queue<pair<int,int>>bb;
            
            bb.push({dist[a],a});
            while(bb.size()){
                auto x = bb.top();
                bb.pop();
                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;
                            bb.push({dist[s.first],s.first});
                        }
                }
            }
            cout << dist[b] << endl;
        }
        
            
        
    }
   
    return 0;
}

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