Submission #231684

#	Time	Username	Problem	Language	Result	Execution time	Memory
231684		Andrei_Cotor	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	492 ms	25572 KiB

commuter_pass

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

vector<pair<int,long long> > A[100005];
long long Dist[2][100005];
long long Dp[4][100005]; //0-inca nu am folosit commuter pass, 1-folosesc commuter pass inspre t, 2-folosesc commuter pass inspre s, 3-am folosit commuter pass

priority_queue<pair<long long,pair<int,int> > > Q;

void getDists(int start1, int start2, int n)
{
    for(int i=1; i<=n; i++)
        Dist[0][i]=Dist[1][i]=1e18;

    Dist[0][start1]=0;
    Dist[1][start2]=0;
    Q.push({0,{0,start1}});
    Q.push({0,{1,start2}});
    while(!Q.empty())
    {
        int wh=Q.top().second.first;
        int nod=Q.top().second.second;
        long long dist=-Q.top().first;
        Q.pop();

        if(dist!=Dist[wh][nod])
            continue;

        for(auto edge:A[nod])
        {
            if(Dist[wh][edge.first]>dist+edge.second)
            {
                Dist[wh][edge.first]=dist+edge.second;
                Q.push({-Dist[wh][edge.first],{wh,edge.first}});
            }
        }
    }
}

void better(int wh, int nod, long long cost)
{
    if(Dp[wh][nod]>cost)
    {
        Dp[wh][nod]=cost;
        Q.push({-cost,{wh,nod}});
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,m,s,t,u,v;
    cin>>n>>m>>s>>t>>u>>v;

    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        cin>>x>>y>>c;

        A[x].push_back({y,c});
        A[y].push_back({x,c});
    }

    getDists(s,t,n);

    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<4; j++)
            Dp[j][i]=1e18;
    }

    Dp[0][u]=0;
    Q.push({0,{0,u}});
    while(!Q.empty())
    {
        int wh=Q.top().second.first;
        int nod=Q.top().second.second;
        long long cost=-Q.top().first;
        Q.pop();

        if(Dp[wh][nod]!=cost)
            continue;

        for(auto edge:A[nod])
        {
            if(wh==0)
            {
                better(0,edge.first,cost+edge.second);

                if(Dist[0][nod]+edge.second+Dist[1][edge.first]==Dist[0][t])
                    better(1,edge.first,cost);
                if(Dist[1][nod]+edge.second+Dist[0][edge.first]==Dist[0][t])
                    better(2,edge.first,cost);
            }
            else if(wh==1)
            {
                if(Dist[0][nod]+edge.second+Dist[1][edge.first]==Dist[0][t])
                    better(1,edge.first,cost);
                
                better(3,edge.first,cost+edge.second);
            }
            else if(wh==2)
            {
                if(Dist[1][nod]+edge.second+Dist[0][edge.first]==Dist[0][t])
                    better(2,edge.first,cost);

                better(3,edge.first,cost+edge.second);
            }
            else
                better(3,edge.first,cost+edge.second);
        }
    }

    cout<<min(min(Dp[0][v],Dp[3][v]),min(Dp[1][v],Dp[2][v]));
    return 0;
}

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