Submission #889414

#	Time	Username	Problem	Language	Result	Execution time	Memory
889414		Alfraganus	Evacuation plan (IZhO18_plan)	C++17	12 / 100	143 ms	16536 KiB

plan

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define str string
#define fastio ios::sync_with_stdio(0), cin.tie(0);
#define fs first
#define ss second
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define len(x) x.size()

#define print(a)          \
    for (auto &x : a)     \
        cout << x << " "; \
    cout << endl;

#define printmp(a)    \
    for (auto &x : a) \
        cout << x.fs << " " << x.ss << endl;

const int mod = 998244353;

void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n + 1);
    for(int i = 0; i < m; i ++){
        int a, b, w;
        cin >> a >> b >> w;
        graph[a].push_back({b, w});
        graph[b].push_back({a, w});
    }
    int g;
    cin >> g;
    vector<int> mins(n + 1, 1e15);
    set<pair<int,int>> s1;
    set<pair<int,int>, greater<pair<int,int>>> s;
    for(int i = 0; i < g; i ++){
        int x;
        cin >> x;
        s1.insert({0, x});
        mins[x] = 0;
    }
    while(!s1.empty()){
        pair<int, int> x = *s1.begin();
        s1.erase(s1.begin());
        for(pair<int, int> y : graph[x.ss]){
            if(mins[y.fs] > x.fs + y.ss){
                s1.erase({mins[y.fs], y.fs});
                mins[y.fs] = x.fs + y.ss;
                s1.insert({mins[y.fs], y.fs});
            }
        }
    }
    int q;
    cin >> q;
    for(int i = 0; i < q; i ++){
        int a, b;
        cin >> a >> b;
        if(n >= 1e3){
            cout << min(mins[a], mins[b]);
            continue;
        }
        vector<int> mn(n + 1);
        s.insert({mins[a], a});
        mn[a] = mins[a];
        while(!s.empty()){
            pair<int, int> x = *s.begin();
            s.erase(s.begin());

            for(auto y : graph[x.ss]){
                if(mn[y.fs] < min(mins[y.fs], x.fs)){
                    s.erase({mn[y.fs], y.fs});
                    mn[y.fs] = min(mins[y.fs], x.fs);
                    s.insert({mn[y.fs], y.fs});
                }
            }
        }
        cout << mn[b] << endl;
    }
}

signed main()
{
    fastio int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
}

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