Submission #1022453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022453		hasan2006	Evacuation plan (IZhO18_plan)	C++17	100 / 100	329 ms	48748 KiB

plan

#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define int long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 1e5 + 9 , mod = 1e9 + 7;
ll   a[N];
ll n , m , q , k;

vector<pair<int,int>>v[N];
set<pair<int,int>>st;

void dijkstra(){
    while(st.size()){
        auto it = st.begin();
        ll x = it->se;
        ll y = it->fi;
        st.erase(it);
        if(a[x] != y)
            continue;
        for(auto to : v[x]){
            if(a[x] + to.se < a[to.fi]){
                a[to.fi] = a[x] + to.se;
                st.insert({a[to.fi] , to.fi});
            }
        }
    }
}

ll sz[N] , p[N] , mn[N];

int get(int n){
    return (p[n] == n ? n : get(p[n]));
}

void join(int x , int y , int k){
    x = get(x);
    y = get(y);
    if(x != y){
        if(sz[x] < sz[y])
            swap(x , y);
        p[y] = x;
        mn[y] = k;
        sz[x] += sz[y];
    }
}

void get1(int x , int y){
    int ans = 1e9;
    while(true){
        if(sz[x] < sz[y]){
            ans = min(ans , mn[x]);
            if(p[x] == y){
                cout<<min(mn[x] , ans)<<"\n";
                return;
            }
            x = p[x];
        }else{
            ans = min(ans , mn[y]);
            if(p[y] == x){
                cout<<min(mn[y] , ans)<<"\n";
                return;
            }
            y = p[y];
        }
        /*if(x == y){
            cout<<0<<"\n";
            return;
        }*/
    }
}

void solve()
{
    cin>>n>>m;
    for(int i = 1; i <= m; i++){
        int x , y , z;
        cin>>x>>y>>z;
        v[x].pb({y , z});
        v[y].pb({x , z});
    }
    cin>>k;
    for(int i = 1; i <= n; i++){
        a[i] = 1e9;
    }
    while(k--){
        int x;
        cin>>x;
        a[x] = 0;
        st.insert({0 , x});
    }
    dijkstra();
    vector<pair<int,int>>g;
    for(int i = 1; i <= n; i++){
        p[i] = i;
        sz[i] = 1;
        g.push_back({a[i] , i});
    }
    sort(rall(g));
    for(auto i : g){
        for(auto to : v[i.se]){
            if(a[to.fi] >= a[i.se]){
                join(i.se , to.fi , a[i.se]);
            }
        }
    }
    cin>>q;
    while(q--){
        int x , y;
        cin>>x>>y;
        get1(x , y);
    }
}

signed main(){
    TL;
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif*/
int t = 1;
//cin>>t;
while(t--)
     {
     solve();
     }
}
// Author : حسن

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