Submission #718731

#	Time	Username	Problem	Language	Result	Execution time	Memory
718731		sofija6	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	822 ms	38812 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define MAXN 100010
#define llinf 1e16
using namespace std;
vector<pair<ll,ll> > G[MAXN];
vector<ll> D[MAXN];
ll n,s,t,u,v,ds[MAXN],du[MAXN],dv[MAXN],dt[MAXN],ans,minu[MAXN],minv[MAXN];
void Dijkstra(ll st,ll *d)
{
    priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
    for (ll i=1;i<=n;i++)
        d[i]=llinf;
    d[st]=0;
    q.push({0,st});
    while (!q.empty())
    {
        ll t=q.top().second,dt=q.top().first;
        q.pop();
        if (d[t]!=dt)
            continue;
        for (auto next : G[t])
        {
            ll i=next.first,c=next.second;
            if (d[t]+c<d[i])
            {
                d[i]=d[t]+c;
                q.push({d[i],i});
            }
        }
    }
}
set<pair<ll,ll> > edges;
void DFS(ll i,ll p)
{
    D[p].push_back(i);
    for (auto next : G[i])
    {
        if (ds[i]+next.second+dt[next.first]==ds[t] && !edges.count({i,next.first}))
        {
            edges.insert({i,next.first});
            DFS(next.first,i);
        }
    }
}
void Dijkstra_Solve()
{
    priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
    for (ll i=1;i<=n;i++)
    {
        minu[i]=llinf;
        minv[i]=llinf;
    }
    minu[s]=du[s];
    minv[s]=dv[s];
    q.push({minu[s],s});
    while (!q.empty())
    {
        ll t=q.top().second,d=q.top().first;
        q.pop();
        if (minu[t]!=d)
            continue;
        ans=min(ans,minu[t]+minv[t]);
        for (ll next : D[t])
        {
            if (minu[next]==llinf)
            {
                minu[next]=du[next];
                minv[next]=dv[next];
                q.push({minu[next],next});
            }
            if (minu[t]<minu[next])
            {
                minu[next]=minu[t];
                minv[next]=min(dv[next],minv[t]);
                q.push({minu[next],next});
                continue;
            }
            if (minu[t]==minu[next] && minv[t]<minv[next])
            {
                minv[next]=minv[t];
                q.push({minu[next],next});
                continue;
            }
        }
    }
    for (ll i=1;i<=n;i++)
    {
        minu[i]=llinf;
        minv[i]=llinf;
    }
    minu[s]=du[s];
    minv[s]=dv[s];
    q.push({minv[s],s});
    while (!q.empty())
    {
        ll t=q.top().second,d=q.top().first;
        q.pop();
        if (minv[t]!=d)
            continue;
        ans=min(ans,minu[t]+minv[t]);
        for (ll next : D[t])
        {
            if (minv[next]==llinf)
            {
                minu[next]=du[next];
                minv[next]=dv[next];
                q.push({minv[next],next});
            }
            if (minv[t]<minv[next])
            {
                minv[next]=minv[t];
                minu[next]=min(du[next],minu[t]);
                q.push({minv[next],next});
                continue;
            }
            if (minv[t]==minv[next] && minu[t]<minu[next])
            {
                minu[next]=minu[t];
                q.push({minu[next],next});
                continue;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll m,a,b,c;
    cin >> n >> m;
    cin >> s >> t >> u >> v;
    for (ll i=1;i<=m;i++)
    {
        cin >> a >> b >> c;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
    }
    Dijkstra(s,ds);
    Dijkstra(u,du);
    Dijkstra(v,dv);
    Dijkstra(t,dt);
    DFS(s,0);
    ans=du[v];
    Dijkstra_Solve();
    cout << ans;
    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45