제출 #1122534

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

plan

#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<random>
#include<cmath>
#include<stack>
#include<map>
#include <iomanip> 
#include <queue>
#include <set>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll mod = 1e9 + 7;
ll pv(ll a, ll b) {
    if (b == 0)return 1;
    ll res = (pv(a, b / 2));
    if (b % 2) {
        return (((res * res) % mod) * (a % mod)) % mod;
    }
    else {
        return (res * res) % mod;
    }
}
ll gcd(ll n1, ll n2)
{
    if (n2 != 0)
        return gcd(n2, n1 % n2);
    else
        return n1;
}


void solve() {
    int n, m; cin >> n >> m;
    vector<vector<pair<int, int>>>  gp(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 });

    }
    int k; cin >> k;
    set<int>st;
    vector<int>erk(n, 0);
    for (int i = 0; i < k; i++) {
        int a; cin >> a;
        a--;
        st.insert(a);
    }
    for (int i = 0; i < n; i++) {
        priority_queue<pair<int, int>> q;
        vector<int>dist(n, 1e9);
        int mn = 1e9;
        q.push({ 0, i });
        dist[i] = 0;

        while (q.size()) {
            int u = q.top().second, aper = q.top().first;
            // cout<<u<<" "<<aper<<endl;
            q.pop();

            if (st.find(u) != st.end()) {
                mn = min(mn, dist[u]);
            }

            if (dist[u] != -aper)continue;
            for (auto x : gp[u]) {
                int v = x.first, w = x.second;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;

                    q.push({ -dist[v], v });
                }
            }
        }
        erk[i] = mn;
    }
    // for(int i=0;i<n;i++){
    //     cout<<mx[i]<<" ";
    // }
    // cout<<endl;
    int q; cin >> q;
    for (int i = 0; i < q; i++) {
        int u1, v1; cin >> u1 >> v1;
        --u1, --v1;
        vector<int>vis(n);
        queue<int>q;
        q.push(u1);
        vector<vector<int>>adj(n);
        while (q.size()) {
            int u = q.front();
            q.pop();
            vis[u] = 1;
            for (auto x : gp[u]) {
                if (vis[x.first] == 0) {
                    vis[x.first] = 1;
                    q.push(x.first);
                    adj[x.first].push_back(u);
                }
            }
        }
        vis.clear();

        int ans = 1e9;
        q.push(v1);
        while (q.size()) {
            int u = q.front();
            q.pop();
            vis[u] = 1;
            ans = min(ans, erk[u]);
            for (auto x : adj[u]) {
                if (vis[x] == 0) {
                    vis[x] = 1;
                    q.push(x);
                }
            }
        }
        cout << ans << endl;


    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cin.tie(nullptr);

    ll _ = 1;
    //cin >> _;
    while (_--)
    {
        solve();
    }
}

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