Submission #716986

#	Time	Username	Problem	Language	Result	Execution time	Memory
716986		ovidiush11	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	900 ms	100536 KiB

commuter_pass

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

#define ll long long
#define ff first
#define ss second

const ll N = 1e5 + 7;

struct node{
    queue<ll> from;
    ll len = 1e18;
};
vector<vector<pair<ll,ll>>> a;
node b[N];
ll dis[N],fdis[N];

void dijsktra1(ll start)
{
    set<pair<ll,pair<ll,ll>>> s;
    s.insert({0,{start,start}});
    while(!s.empty())
    {
        pair<ll,pair<ll,ll>> v = *s.begin();
        s.erase(s.begin());
        if(v.ff > b[v.ss.ff].len)continue;
        dis[v.ss.ff] = max(dis[v.ss.ff],dis[v.ss.ss] + 1);
        if(v.ff == b[v.ss.ff].len)
        {
            b[v.ss.ff].from.push(v.ss.ss);
            continue;
        }
        b[v.ss.ff].len = v.ff;
        b[v.ss.ff].from = queue<ll>();
        b[v.ss.ff].from.push(v.ss.ss);
        for(auto x : a[v.ss.ff])s.insert({b[v.ss.ff].len + x.ff,{x.ss,v.ss.ff}});
    }
    b[start].from.pop();
    return;
}


void correct(ll start)
{
    queue<ll> q;
    q.push(start);
    while(!q.empty())
    {
        ll v = q.front();
        q.pop();
        if(fdis[v] != -1)continue;
        fdis[v] = dis[v];
        while(!b[v].from.empty())
        {
            q.push(b[v].from.front());
            b[v].from.pop();
        }
    }
    return ;
}

ll st[N],dis2[N];

void dijsktra2(ll start)
{
    set<pair<ll,pair<ll,ll>>> s;
    s.insert({0,{start,-1}});
    while(!s.empty())
    {
        pair<ll,pair<ll,ll>> v = *s.begin();
        s.erase(s.begin());
        if(v.ff > dis2[v.ss.ff])continue;
        if(st[v.ss.ff] == 2)continue;
        if(st[v.ss.ff] == 1 && v.ss.ss > -1)continue;
        if(v.ss.ss == -1)st[v.ss.ff] = 2;
        else st[v.ss.ff] = 1;
        dis2[v.ss.ff] = v.ff;
        for(auto x : a[v.ss.ff])
        {
            if(v.ss.ss == -1)
            {
                s.insert({dis2[v.ss.ff] + x.ff,{x.ss,-1}});
                if(fdis[v.ss.ff] < fdis[x.ss] && fdis[x.ss] != -1 && fdis[v.ss.ff] != -1)s.insert({dis2[v.ss.ff],{x.ss,0}});
                else if(fdis[v.ss.ff] != -1 && fdis[x.ss] != -1)s.insert({dis2[v.ss.ff],{x.ss,1}});
            }
            else if(v.ss.ss == 0)
            {
                if(fdis[v.ss.ff] < fdis[x.ss] && fdis[v.ss.ff] != -1 && fdis[x.ss] != -1)s.insert({dis2[v.ss.ff],{x.ss,0}});
                s.insert({dis2[v.ss.ff] + x.ff,{x.ss,2}});
            }
            else if(v.ss.ss == 1)
            {
                if(fdis[v.ss.ff] > fdis[x.ss] && fdis[v.ss.ff] != -1 && fdis[x.ss] != -1)s.insert({dis2[v.ss.ff],{x.ss,1}});
                else s.insert({dis2[v.ss.ff] + x.ff,{x.ss,2}});
            }
            else s.insert({dis2[v.ss.ff] + x.ff,{x.ss,2}});
        }
    }
    return ;
}

int main()
{
    ll n,m,s,t,u,v;
    cin>>n>>m;
    cin>>s>>t;
    cin>>u>>v;
    s--;t--;u--;v--;
    a.resize(n);
    for(ll i = 0;i < n;i++)fdis[i] = -1;
    for(ll i = 0;i < n;i++)dis2[i] = 1e18;
    for(ll i = 0;i < m;i++)
    {
        ll x,y,z;
        cin>>x>>y>>z;x--;y--;
        a[x].push_back({z,y});
        a[y].push_back({z,x});
    }
    dijsktra1(s);
    correct(t);
    //cout<<b[t].len<<" ";
    dijsktra2(u);
    cout<<dis2[v]<<" ";
}
/*
6 7
2 4
2 4
1 2 1
1 6 2
2 6 3
2 5 1
2 3 4
3 4 2
6 4 3
*/

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