Submission #565810

#	Time	Username	Problem	Language	Result	Execution time	Memory
565810		Majid	Evacuation plan (IZhO18_plan)	C++17	23 / 100	591 ms	31696 KiB

plan

#include<bits/stdc++.h>
using namespace std;
 
//Types
using ll = long long;
using db = double;
 
//Vectors
#define pb push_back
#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(), vec.end()
 
//things
#define f first
#define s second
const int SMALLINF = 1e9 + 7;
const ll BIGINF = ((ll)1e18) + 7;
#define Speeed ios::sync_with_stdio(0);cin.tie(NULL); cout.tie(NULL);

vector<pair<ll, ll> > connect[100007];
vector<bool> mark(100007);
//vector<bool> visited(100007);
map<ll, bool> visited;
vector<ll> dist(100007, BIGINF);

void find(ll x){
    
    priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > pq;
    pq.push({0, x});
    // visited[x] = true;
    
    while(!pq.empty()){
        
        ll u = pq.top().s, w = pq.top().f;
        pq.pop();
        // visited[u] = tru
            
            // if(mark[u])dist[x] = min(dist[x], w); 
            // visited[u] = true;
        for(auto v: connect[u]){
            
            // if(!visited[v.s]){
                
                if(w+v.f<dist[v.s]){
                    
                    dist[v.s] = w+v.f;
                    pq.push({dist[v.s], v.s});
                }
                
                // visited[v.s] = true;
            // }   
        }
        
        // cout<<u<<" ";
    
    // cout<<"\n";
}
}

void solve(){

    ll n, m, k, q;
    cin>>n>>m;
    
    for(ll i = 0; i < m; i++){
        
        ll u, v, w;
        cin>>u>>v>>w;
        
        connect[u].pb({w, v});
        connect[v].pb({w, u});
    }
    
    cin>>k;
    
    for(ll i = 0; i < k; i++){
        
        ll x;
        cin>>x;
        // mark[x] = true;
        dist[x] = 0;
        // pq.push({0, x});
        find(x);
    }
    
    // find();
    
    cin>>q;
    
    
    while(q--){
    
        ll s, t;
        cin>>s>>t;
    
        cout<<min(dist[s], dist[t])<<"\n";
        // cout<<dist[s]<<" "<<dist[t]<<"\n";
    }
}


int main(){
	Speeed
	
    ll t=1;
    // cin>>t;
    
    while(t--){
        
        solve();
    }
}

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