Submission #717266

#	Time	Username	Problem	Language	Result	Execution time	Memory
717266		ovidiush11	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	1308 ms	262144 KiB

commuter_pass

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

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

const ll N = 1e5+7;

ll n,m,s,t,u,v;
vector<vector<pair<ll,ll>>> a;
vector<queue<ll>> from;
ll dis[N],len[N],flen[N];

void dijsktra1()
{
    priority_queue<pair<ll,pair<ll,ll>>> pq;
    pq.push(mp(0,mp(s,s)));
    for(ll i = 0;i < n;i++){dis[i] = 1e18;len[i] = 0;flen[i] = 0;}
    while(!pq.empty())
    {
        pair<ll,pair<ll,ll>> v = pq.top();
        pq.pop();v.ff *= -1;
        if(dis[v.ss.ff] < v.ff)continue;
        len[v.ss.ff] = max(len[v.ss.ff],len[v.ss.ss] + 1);
        if(dis[v.ss.ff] == v.ff){from[v.ss.ff].push(v.ss.ss);continue;}
        dis[v.ss.ff] = v.ff;
        from[v.ss.ff] = queue<ll>();
        from[v.ss.ff].push(v.ss.ss);
        for(auto x : a[v.ss.ff])pq.push(mp(-(x.ff+dis[v.ss.ff]),mp(x.ss,v.ss.ff)));
    }
    return ;
}

ll st[N];

void check()
{
    queue<ll> q;
    q.push(t);
    while(!q.empty())
    {
        ll v = q.front();
        q.pop();
        if(st[v] == 1)continue;
        st[v] = 1;flen[v] = len[v];
        while(!from[v].empty())
        {
            q.push(from[v].front());
            from[v].pop();
        }
    }
}

ll dis2[N],st2[N];

void dijsktra2()
{
    priority_queue<pair<ll,pair<ll,ll>>> pq;
    pq.push(mp(0,mp(u,-1)));
    for(ll i = 0;i < n;i++)dis2[i] = 1e18;
    for(ll i = 0;i < n;i++)st2[i] = 0;
    while(!pq.empty())
    {
        pair<ll,pair<ll,ll>> v = pq.top();
        pq.pop();v.ff *= -1;
        if(st2[v.ss.ff] == -1)continue;
        if(v.ss.ss == -1)st2[v.ss.ff] = -1;
        else if((v.ss.ss == 0 || v.ss.ss == 1) && (st2[v.ss.ff] == 1 && st2[v.ss.ff] == 3))continue;
        else if(v.ss.ss == -2 && (st2[v.ss.ff] == 2 || st2[v.ss.ff] == 3))continue;
        else st2[v.ss.ff] += abs(v.ss.ss);
        dis2[v.ss.ff] = min(v.ff,dis2[v.ss.ff]);
        for(auto x : a[v.ss.ff])
        {
            if(st2[v.ss.ff] == -1)
            {
                if(flen[x.ss] != 0 && flen[v.ss.ff] != 0){
                    if(flen[x.ss] < flen[v.ss.ff])pq.push(mp(-(v.ff),mp(x.ss,0)));
                    else pq.push(mp(-(v.ff),mp(x.ss,1)));
                }
                pq.push(mp(-(v.ff+x.ff),mp(x.ss,-1)));
            }
            else if(st2[v.ss.ff] == 0)
            {
                if(flen[x.ss] != 0 && flen[v.ss.ff] != 0 && flen[x.ss] < flen[v.ss.ff])pq.push(mp(-(v.ff),mp(x.ss,0)));
                else pq.push(mp(-(v.ff+x.ff),mp(x.ss,-2)));
            }
            else if(st2[v.ss.ff] == 1)
            {
                if(flen[x.ss] != 0 && flen[v.ss.ff] != 0 && flen[x.ss] > flen[v.ss.ff])pq.push(mp(-(v.ff),mp(x.ss,1)));
                else pq.push(mp(-(v.ff+x.ff),mp(x.ss,-2)));
            }
            else pq.push(mp(-(v.ff+x.ff),mp(x.ss,-2)));
        }
    }
    return ;
}

int main()
{
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    cin>>s>>t;s--;t--;
    cin>>u>>v;u--;v--;
    a.resize(n);from.resize(n);
    for(ll i = 0;i < m;i++)
    {
        ll x,y,z;
        cin>>x>>y>>z;x--;y--;
        a[x].push_back(mp(z,y));
        a[y].push_back(mp(z,x));
    }
    dijsktra1();
    check();
    dijsktra2();
    cout<<dis2[v];
    return 0;
}

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