Submission #957178

#	Time	Username	Problem	Language	Result	Execution time	Memory
957178		ezzzay	Evacuation plan (IZhO18_plan)	C++14	0 / 100	1 ms	604 KiB

plan

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=1e3+5;
vector<pair<int,int>>v[N];
int dist[N];
vector<int>ans;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        dist[i]=1e14;
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    int k;
    cin>>k;
    priority_queue<pair<int,int>>q;
    for(int i=1;i<=k;i++){
        int a;
        cin>>a;
        dist[a]=0;
        q.push({0,a});
    }
    while(!q.empty()){
        int a=q.top().ss;
        int w= -q.top().ff;
        q.pop();
        if(dist[a]<w)continue;
        for(auto p:v[a]){
            int b=p.ff;
            int c=p.ss;
            if(dist[b]>dist[a]+c){
                dist[b]=dist[a]+c;
                q.push({-dist[b],b});
            }
        }
    }
    
    int qr;
    cin>>qr;
    while(qr--){
        int x,y;
        cin>>x>>y;
        int tmp[N];
        for(int i=1;i<=n;i++){
            tmp[i]=1e14;
        }
        
        tmp[x]=0;
        int par[N];
        par[x]=x;
        priority_queue<pair<int,int>>q;
        while(!q.empty())q.pop();
        q.push({0,x});
        while(!q.empty()){
            int a=q.top().ss;
            int w= -q.top().ff;
            q.pop();
            if(tmp[a]<w)continue;
            for(auto p:v[a]){
                int b=p.ff;
                int c=p.ss;
                if(tmp[b]>tmp[a]+c){
                    par[b]=a;
                    tmp[b]=tmp[a]+c;
                    q.push({-tmp[b],b});
                }
            }
        }
        int z=min(dist[y],dist[x]);
        while(y!=x){
          
            z=min(z,dist[y]);
            y=par[y];
        }
        //cout<<endl;
        ans.pb(z);
    }
    
    for(auto z:ans)cout<<z<<endl;
}

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