Submission #75468

#	Time	Username	Problem	Language	Result	Execution time	Memory
75468		vex	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	631 ms	96432 KiB

commuter_pass

#include <bits/stdc++.h>
#define maxn 100005
#define pii pair<int,int>
#define INF 100000000000000000
using namespace std;

int n,m;
vector<pii>adj[maxn];
int s,t;
long long ds[maxn];
long long dt[maxn];
long long duu[maxn];
int u,v;
long long du[maxn][3];
int first[maxn];
//0 nije poceo
//1 traje
//2 prosao
vector<int>mv[3];

priority_queue<pair<long long,int>>pq;
priority_queue<pair<long long,pii>>pq2;

long long manji(long long aa,long long bb)
{
    if(aa<bb)return aa;
    return bb;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    mv[0].push_back(0);
    mv[0].push_back(1);
    mv[1].push_back(1);
    mv[1].push_back(2);
    mv[2].push_back(2);

    cin>>n>>m;
    cin>>s>>t;
    cin>>u>>v;
    for(int i=0;i<m;i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        adj[x].push_back({y,c});
        adj[y].push_back({x,c});
    }
    //cout<<endl;

    for(int i=1;i<=n;i++)ds[i]=INF;
    pq.push({0LL,s});
    ds[s]=0LL;
    while(!pq.empty())
    {
        int x=pq.top().second;
        pq.pop();

        for(auto zz:adj[x])
        {
            int y=zz.first;
            int ras=zz.second;
            if(ds[y]>ds[x]+ras)
            {
                ds[y]=ds[x]+ras;
                pq.push({-ds[y],y});
            }
        }
    }
    //for(int i=1;i<=n;i++)cout<<i<<" "<<ds[i]<<endl;cout<<endl;

    for(int i=1;i<=n;i++)dt[i]=INF;
    pq.push({0LL,t});
    dt[t]=0LL;
    while(!pq.empty())
    {
        int x=pq.top().second;
        pq.pop();

        for(auto zz:adj[x])
        {
            int y=zz.first;
            int ras=zz.second;
            if(dt[y]>dt[x]+ras)
            {
                dt[y]=dt[x]+ras;
                pq.push({-dt[y],y});
            }
        }
    }
    //for(int i=1;i<=n;i++)cout<<i<<" "<<dt[i]<<endl;cout<<endl;

    for(int i=1;i<=n;i++)duu[i]=INF;
    pq.push({0LL,u});
    duu[u]=0LL;
    while(!pq.empty())
    {
        int x=pq.top().second;
        pq.pop();

        for(auto zz:adj[x])
        {
            int y=zz.first;
            int ras=zz.second;
            if(duu[y]>duu[x]+ras)
            {
                duu[y]=duu[x]+ras;
                pq.push({-duu[y],y});
            }
        }
    }
    //for(int i=1;i<=n;i++)cout<<i<<" "<<duu[i]<<endl;cout<<endl;

    for(int i=1;i<=n;i++)du[i][0]=du[i][1]=du[i][2]=INF;
    pq2.push({0LL,{u,0}});
    pq2.push({0LL,{u,2}});
    du[u][0]=0LL;
    du[u][2]=0LL;

    du[u][1]=0LL;
    first[u]=u;
    if(ds[u]+dt[u]!=ds[t])du[u][1]=INF;
    pq2.push({-du[u][1],{u,1}});

    while(!pq2.empty())
    {
        int x=pq2.top().second.first;
        int ty=pq2.top().second.second;
        pq2.pop();

        for(auto zz:adj[x])
        {
            int y=zz.first;
            for(auto tt:mv[ty])
            {
                int ras=zz.second;
                int prvi=first[x];
                if(ty!=1)prvi=x;

                if(tt==1)
                {
                    //if(x==2 && ty==0 && y==1 && tt==1)cout<<"qrac1 "<<y<<" "<<prvi<<" "<<ds[prvi]<<" "<<dt[y]<<" "<<duu[x]<<" "<<duu[prvi]<<" "<<ras<<" "<<ds[t]<<endl;
                    long long resss=manji(ds[prvi]+dt[y],dt[prvi]+ds[y]);
                    if(resss+duu[x]-duu[prvi]+ras!=ds[t])continue;
                    //if(x==2 && ty==0 && y==1 && tt==1)cout<<"qrac2"<<endl;
                    ras=0;
                }


                if(du[y][tt]>du[x][ty]+ras)
                {
                    du[y][tt]=du[x][ty]+ras;
                    pq2.push({-du[y][tt],{y,tt}});
                    if(tt==1)first[y]=prvi;
                }
            }
        }
    }

    //for(int i=1;i<=n;i++)cout<<i<<"   "<<du[i][0]<<" "<<du[i][1]<<" "<<du[i][2]<<endl;

    long long sol=du[v][0];
    if(sol>du[v][1])sol=du[v][1];
    if(sol>du[v][2])sol=du[v][2];

    cout<<sol<<endl;
    return 0;
}

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