제출 #1199221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199221		prikpao	Evacuation plan (IZhO18_plan)	C++20	0 / 100	89 ms	10944 KiB

plan

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define st first
#define nd second
#define pb push_back
#define ins insert
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define t3 tuple<int, int, int>
#define t4 tuple<int, int, int, int>
#define chmn(a, b) a=min(a, b)
#define chmx(a, b) a=max(a, b)
#define For(i, a, b) for(int i=(int)a; i<=(int)b; i++)
#define Forx(i, a, b, x) for(int i=(int)a; i<=(int)b; i+=(int)x)
#define F0r(i, n) for(int i=0; i<(int)n; i++)
#define Rof(i, a, b) for(int i=(int)a; i>=(int)b; i--)
#define R0f(i, n) for(int i=(int)(n-1); i>=(int)0; i--)
#define rep(n) F0r(_, (int)n)
#define all(v) (v).begin(), (v).end()
const int N = 1e5+5;
using ll = long long;
using namespace std;

struct A{
    int a, w, mn;
    bool operator<(const A& o)const{
        return w>o.w;
    }
};
struct B{
    int a, w;
    bool operator<(const B& o)const{
        return w>o.w;
    }
};

int dis[N], dis2[N];
vector<B> g[N];

void solve(){
    int n, m, k, q, a, b, w, s, t;
    cin >> n >> m;
    rep(m){
        cin >> a >> b >> w;
        g[a].pb({b, w});
        g[b].pb({a, w});
    }
    cin >> k;
    priority_queue<B> pq;
    fill(dis+1, dis+n+1, 1e9);
    rep(k){
        cin >> a;
        pq.push({a, 0});
        dis[a]=0;
    }
    while(!pq.empty()){
        auto [a,w]=pq.top();
        pq.pop();

        if(w>dis[a])continue;
        for(auto i:g[a]){
            if(w+i.w<dis[i.a]){
                dis[i.a]=w+i.w;
                pq.push({i.a, w+i.w});
            }
        }
    }
    cin >> q;
    priority_queue<A> pq2;
    rep(q){
        while(!pq2.empty())pq2.pop();
        cin >> s >> t;
        fill(dis2+1, dis2+n+1, 1e9);
        dis2[s]=0;
        pq2.push({s, 0, dis[s]});
        while(!pq2.empty()){
            auto [a,w,mn]=pq2.top();
            pq2.pop();

            if(w>dis2[a])continue;
            if(a==t){
                cout << mn << '\n';
                break;
            }
            for(auto i:g[a]){
                if(w+i.w<dis2[i.a]){
                    dis2[i.a]=w+i.w;
                    pq2.push({i.a, w+i.w, min(mn, dis[i.a])});
                }
            }
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    int Tcases=1;
    //cin >> Tcases;
    while(Tcases--)solve();
    return 0;
}

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