Submission #90442

#	Time	Username	Problem	Language	Result	Execution time	Memory
90442		Abelyan	Evacuation plan (IZhO18_plan)	C++17	23 / 100	746 ms	28312 KiB

plan

#include <bits/stdc++.h>
using namespace std;
 
const int N=500005;
const int LG=log2(N)+3;
 
#define fr first
#define sc second
 
vector<pair<int,int> > g[N];
int dp[N];
bool col[N];
 
int main(){
    ios_base::sync_with_stdio(false);
    //freopen("input.txt","r",stdin);
    int n,m;
    cin>>n>>m;
    for (int i=0;i<m;i++){
        int a,b,l;
        cin>>a>>b>>l;
        g[a].push_back({b,l});
        g[b].push_back({a,l});
    }
    for (int i=1;i<=n;i++){
        dp[i]=INT_MAX;
    }
    priority_queue<pair<int,int> > pq;
    int blackNum;
    cin>>blackNum;
    for (int i=0;i<blackNum;i++){
        int k;
        cin>>k;
        dp[k]=0;
        pq.push({0,k});
    }
    while (!pq.empty()){
        int cur;
        do{
            cur=pq.top().sc;
            pq.pop();
        }while(col[cur] && !pq.empty());
        if (col[cur])break;
        col[cur]=true;
        for (auto to:g[cur]){
            if (dp[cur]+to.sc<dp[to.fr]){
                dp[to.fr]=dp[cur]+to.sc;
                pq.push({-dp[to.fr],to.fr});
            }
        }
    }
  	int q;
    cin>>q;
    for (int i=0;i<q;i++){
        int a,b;
        cin>>a>>b;
        cout<<min(dp[a],dp[b])<<endl;
    }
    return 0;
}

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