Submission #718447

#	Time	Username	Problem	Language	Result	Execution time	Memory
718447		ovidiush11	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	721 ms	27124 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;

ll pos[4],dis[4][N],n,m;
vector<vector<pair<ll,ll>>> a;

void dijkstra(ll p)
{
    priority_queue<pair<ll,ll>> pq;
    pq.push({0,pos[p]});
    for(ll i = 0;i < n;i++)dis[p][i] = 1e18;
    while(!pq.empty())
    {
        pair<ll,ll> v = pq.top();
        pq.pop();
        v.ff *= -1;
        if(v.ff >= dis[p][v.ss])continue;
        dis[p][v.ss] = v.ff;
        for(auto x : a[v.ss])pq.push(make_pair(-(v.ff + x.ff),x.ss));
    }
    return ;
}

ll in[N],len[N];

void check(ll p)
{
    for(ll i = 0;i < n;i++)in[i] = 0;
    for(ll i = 0;i < n;i++)len[i] = 0;
    priority_queue<pair<ll,pair<ll,ll>>> pq;
    pq.push(make_pair(-dis[1][p],make_pair(p,p)));
    while(!pq.empty())
    {
        pair<ll,pair<ll,ll>> v = pq.top();
        pq.pop();
        len[v.ss.ff] = max(len[v.ss.ff],len[v.ss.ss] + 1);
        if(in[v.ss.ff])continue;
        in[v.ss.ff] = 1;
        for(auto x : a[v.ss.ff]){
            if(dis[0][x.ss] + dis[1][x.ss] == dis[1][pos[0]] && dis[1][x.ss] > dis[1][v.ss.ff]){
                pq.push(make_pair(-dis[1][x.ss],make_pair(x.ss,v.ss.ff)));
            }
        }
    }
}

ll dismin[N][2],st[N];

void getmin(ll s)
{
    for(ll i = 0;i < n;i++)dismin[i][s] = dis[2][i];
    for(ll i = 0;i < n;i++)st[i] = 0;
    priority_queue<pair<ll,pair<ll,ll>>> pq;
    if(s == 1)pq.push(make_pair(-len[pos[s]],make_pair(pos[s],pos[s])));
    else pq.push(make_pair(len[pos[s]],make_pair(pos[s],pos[s])));
    while(!pq.empty())
    {
        pair<ll,pair<ll,ll>> v = pq.top();
        pq.pop();
        dismin[v.ss.ff][s] = min(dismin[v.ss.ff][s],dismin[v.ss.ss][s]);
        if(st[v.ss.ff])continue;
        st[v.ss.ff] = 1;
        for(auto x : a[v.ss.ff])
        {
            if(in[x.ss])
            {
                if(s == 1 && len[x.ss] > len[v.ss.ff])pq.push(make_pair(-len[x.ss],make_pair(x.ss,v.ss.ff)));
                else if(s == 0 && len[x.ss] < len[v.ss.ff])pq.push(make_pair(len[x.ss],make_pair(x.ss,v.ss.ff)));
            }
        }
    }
    return ;
}

int main()
{
    cin>>n>>m;
    cin>>pos[0]>>pos[1]>>pos[2]>>pos[3];
    pos[0]--;pos[1]--;pos[2]--;pos[3]--;
    a.resize(n);
    for(ll i = 0;i < m;i++)
    {
        ll x,y,z;
        cin>>x>>y>>z;x--;y--;
        a[x].push_back(make_pair(z,y));
        a[y].push_back(make_pair(z,x));
    }
    dijkstra(0);dijkstra(1);dijkstra(2);dijkstra(3);
    check(pos[1]);
    getmin(0);
    getmin(1);
    ll ans = dis[2][pos[3]];
    for(ll i = 0;i < n;i++)if(in[i])ans = min(min(dismin[i][0],dismin[i][1]) + dis[3][i],ans);
    cout<<ans;
    return 0;
}

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