Submission #1045455

#TimeUsernameProblemLanguageResultExecution timeMemory
1045455vjudge1Evacuation plan (IZhO18_plan)C++17
100 / 100
337 ms59468 KiB
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second

typedef long long ll;
typedef pair<ll,ll> pli;

const ll maxn=1e5+5;
const ll inf=1e18;

ll n,m,k,q,x,y,z,w,a[maxn];
vector<pair<ll,ll>> adj[maxn];
ll dist[maxn];
ll parent[maxn],id[maxn],sz[maxn];
set<ll> s[maxn];
ll ans[maxn];
bool mark[maxn];

void dijkstra()
{
    fill(dist+1,dist+n+1,inf);
    priority_queue<pli,vector<pli>,greater<pli>> pq;
    for (ll i=1;i<=k;i++)
    {
        dist[a[i]]=0;
        pq.push({0,a[i]});
    }
    while (!pq.empty())
    {
        ll u=pq.top().se;
        ll t=pq.top().fi;
        pq.pop();
        if (t>dist[u]) continue;
        for (auto e:adj[u])
        {
            ll v=e.fi;
            ll w=e.se;
            if (dist[v]>dist[u]+w)
            {
                dist[v]=dist[u]+w;
                pq.push({dist[v],v});
            }
        }
    }
}

ll find_set(ll u)
{
    if (u==parent[u]) return u;
    return parent[u]=find_set(parent[u]);
}

void union_set(ll u,ll v)
{
    u=find_set(u);
    v=find_set(v);
    if (u==v) return;
    if (sz[v]>sz[u]) swap(u,v);
    parent[v]=u;
    sz[u]+=sz[v];
    for (ll x:s[v])
    {
        if (s[u].find(x)!=s[u].end())
        {
            s[u].erase(x);
            ans[x]=w;
        }
        else s[u].insert(x);
    }
}

bool cmp(ll a,ll b)
{
    return dist[a]>dist[b];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    while (m--)
    {
        cin>>x>>y>>z;
        adj[x].push_back({y,z});
        adj[y].push_back({x,z});
    }
    cin>>k;
    for (ll i=1;i<=k;i++)
    {
        cin>>a[i];
    }
    dijkstra();
    cin>>q;
    for (ll i=1;i<=q;i++)
    {
        cin>>x>>y;
        s[x].insert(i);
        s[y].insert(i);
    }
    for (ll i=1;i<=n;i++)
    {
        id[i]=i;
        parent[i]=i;
        sz[i]=1;
    }
    sort(id+1,id+n+1,cmp);
    memset(mark,0,sizeof(mark));
    for (ll i=1;i<=n;i++)
    {
        x=id[i];
        mark[x]=true;
        w=dist[x];
        for (auto it:adj[x])
        {
            y=it.fi;
            if (mark[y]) union_set(x,y);
        }
    }
    for (ll i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...