Submission #893025

#	Time	Username	Problem	Language	Result	Execution time	Memory
893025		vjudge1	Evacuation plan (IZhO18_plan)	C++17	0 / 100	470 ms	32572 KiB

plan

// 以上帝的名义
// 候选硕士
#include <bits/stdc++.h>

#ifdef local
#include "algo/debug.h"
#else
#define dbg(x...) 0
#endif

using namespace std ;
using ll = long long ;

template<class T> constexpr T inf = ::numeric_limits<T>::max() / 32 * 15 + 208;

const int N = 1e5 + 5 ;

int n , m , k , city[N] ;
ll dist[N], pr[N] ;
vector<pair<ll,int>> g[N] ;

void djickstra() {
    for (int i = 1 ; i <= n ; i++) {
        dist[i] = inf<ll> ;
        pr[i] = -1 ;
    }
    set<pair<ll,int>> st;
    for (int i = 0 ; i < k ; i++) {
        st.insert({0, city[i]}) ;
        dist[city[i]] = 0 ;
    }
    while (st.size()) {
        auto [val, v] = *st.begin() ;
        st.erase(st.begin()) ;
        for (auto [w, to] : g[v]) {
            if (dist[to] > dist[v] + w) {
                st.erase({dist[to], to}) ;
                dist[to] = dist[v] + w ;
                pr[to] = v ;
                st.insert({dist[to], to}) ;
            }
        }
    }
}

vector<int> order ;

ll calc(int mid, int s, int t) {
    vector<int> is(n + 1, 0) ;
    for (int i = 0 ; i < mid ; i++) {
        is[order[i]] = 1 ;
    }
    if (!is[s] || !is[t]) return -1 ;
    vector<int> use(n + 1, 0) ;
    queue<int> q ;
    q.push(s) ;
    pr[s] = -1 ;
    use[s] = 1 ;
    while (q.size()) {
        int v = q.front() ;
        q.pop() ;
        for (auto [w, to] : g[v]) {
            if (!is[to] || use[to]) continue ;
            pr[to] = v ;
            q.push(to) ;
            use[to] = 1 ;
        }
    }
    if (!use[t]) {
        return -1 ;
    }
    ll ret = inf<ll> ;
    for (int i = t ; i != pr[s] ; i = pr[i]) {
        ret = min(ret, dist[i]) ;
    }
    return ret ;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(false) ;
    cin >> n >> m ;
    for (int i = 0 ; i < m ; i++) {
        ll u , v , w ; cin >> u >> v >> w ;
        g[u].push_back({w, v}) ;
        g[v].push_back({w, u}) ;
    }
    cin >> k ;
    for (int i = 0 ; i < k ; i++) {
        cin >> city[i] ;
    }
    djickstra() ;
    for (int i = 1 ; i <= n ; i++) order.push_back(i) ;
    sort(order.begin(), order.end(), [&](int u, int v){
        return dist[u] > dist[v] ;
    }) ;
    int q ; cin >> q ;
    for (int i = 0 ; i < q ; i++) {
        int u , v ; cin >> u >> v ;
        int l = 0 , r = n - 1 ;
        while (l < r) {
            int mid = (l + r) / 2 ;
            if (calc(mid, u, v) != -1) r = mid ;
            else l = mid + 1 ;
        }
        cout << calc(r, u, v) << "\n" ;
    }
    return 0 ;
}

// 希望白银

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