Submission #1123978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123978		boris_7	Evacuation plan (IZhO18_plan)	C++20	54 / 100	367 ms	22324 KiB

plan

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

vector<vector<pair<int,int>>>gp;

void solve() {
    int n,m;
    cin>>n>>m;
    gp = vector<vector<pair<int,int>>>(n);
    for(int i = 0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        --u,--v;
        gp[u].push_back({v,w});
        gp[v].push_back({u,w});
    }
    set<pair<int,int>>pq;
    vector<int>d(n,INT_MAX);
    int q;
    cin>>q;
    while(q--){
        int u;
        cin>>u;
        --u;
        pq.insert({0,u});
        d[u]=0;
    }
    while(pq.size()){
        int u = (*pq.begin()).second;
        int dist = (*pq.begin()).first;
        pq.erase(pq.begin());
        if(d[u]!=dist) continue;
        for(pair<int,int> &i:gp[u]){
            if(dist+i.second<d[i.first]){
                d[i.first]=dist+i.second;
                pq.insert({d[i.first],i.first});
            }
        }
    }
    cin>>q;
    if(q>1e3){
        while(q--){
            int u,v;
            cin>>u>>v;
            --u,--v;
            cout<<min(d[u],d[v])<<endl;
        }
        return;
    }
    while(q--){
        int u,v;
        cin>>u>>v;
        --u,--v;
        vector<int>dd(n,0);
        dd[u]=d[u];
        pq.insert({dd[u],u});
        while(pq.size()){
            int u = (*pq.rbegin()).second;
            int dist = (*pq.rbegin()).first;
            pq.erase({dist,u});
            if(dd[u]!=dist) continue;
            for(pair<int,int> &i:gp[u]){
                if(min(dist,d[i.first])>dd[i.first]){
                    dd[i.first]=min(dist,d[i.first]);
                    pq.insert({dd[i.first],i.first});
                }
            }
        }
        cout<<dd[v]<<endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    // ll t;cin>>t;while(t--)
        solve();
}

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