제출 #565592

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

plan

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>>vct[n+1];
    map<int,bool>mp[n+1];
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        mp[u][v]=1;
        mp[v][u]=1;
        vct[u].push_back({v,w});
        vct[v].push_back({u,w});
    }
    vector<int>dan(n+1,-1);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    int k;
    cin>>k;
    while(k--){
        int x;
        cin>>x;
        pq.push({0,x});
    }
    while(pq.size()){
        int b=pq.top().first,a=pq.top().second;
        pq.pop();
        if(dan[a]!=-1)continue;
        dan[a]=b;
        for(auto &i:vct[a]){
            if(dan[i.first]==-1){
                pq.push({b+i.second,i.first});
            }
        }
    }
    int q;
    cin>>q;
    while(q--){
        int u,v;
        cin>>u>>v;
        if(mp[u][v]){cout<<min(dan[u],dan[v])<<endl;continue;}
        while(pq.size())pq.pop();
        vector<bool>vis(n+1);
        pq.push({-dan[u],u});
        while(pq.size()){
            int b=pq.top().first,a=pq.top().second;
            pq.pop();
            if(vis[a])continue;
            if(a==v){cout<<-b<<endl;break;}
            vis[a]=1;
            for(auto &i:vct[a]){
                if(!vis[i.first]){
                    pq.push({-min(dan[i.first],-b),i.first});
                }
            }
        }
    }
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

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