제출 #1096103

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1096103		I_FloPPed21	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	239 ms	29856 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+1;
const long long infinit=1e18;
int n,m,casa,scoala,mag1,mag2;
long long costuri[N];
vector<int>pereche[N];
long long dp[N][2][3];//directie drum pentru 1/astfel 1 egal crescator 2 descrescator 0 bag pula;
struct drum
{
    int unde,cost;
};
struct coada
{
    int nod;
    long long cost;
    int a_folosit;//asta e de 3 tipuri
    int drumulet;
};

struct compara
{
    bool operator()(coada &x,coada &y)
    {
        return x.cost>y.cost;
    }
};

void reset()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<2; j++)
            for(int k=0; k<3; k++)
                dp[i][j][k]=infinit;
    }
}
vector<drum>adj[N];
void cauta_drum(int start)
{
    for(int i=1; i<=n; i++)
        costuri[i]=infinit;
    priority_queue<coada,vector<coada>,compara>pq;
    reset();
    costuri[start]=0;
    coada x= {start,0,0,0};
    pq.push(x);
    while(!pq.empty())
    {
        coada actual=pq.top();
        pq.pop();
        for(auto u:adj[actual.nod])
        {
            if(costuri[u.unde]>actual.cost+u.cost)
            {
                costuri[u.unde]=actual.cost+u.cost;
                pq.push({u.unde,costuri[u.unde],0});
            }
        }
    }
}
void back_drum(int start)
{
    queue<int>cod;
    cod.push(start);
    vector<bool>viz(n+1,0);
    viz[start]=true;
    while(!cod.empty())
    {
        int nod=cod.front();
        cod.pop();

        for(auto u:adj[nod])
        {
            if(costuri[u.unde]+u.cost==costuri[nod])
            {
                pereche[u.unde].push_back(nod);
                pereche[nod].push_back(u.unde);
                if(!viz[u.unde])
                {
                    viz[u.unde]=true;
                    cod.push(u.unde);
                }
            }
        }
    }
}

void calculeaza_cost(int start)
{
    reset();
    priority_queue<coada,vector<coada>,compara>pq;
    dp[start][0][0]=0;
    pq.push({start,0,0,0});
    while(!pq.empty())
    {
        int nod,tip;
        long long cost;
        nod=pq.top().nod;
        cost=pq.top().cost;
        tip=pq.top().a_folosit;
        int drum=pq.top().drumulet;
        pq.pop();
        for(auto u:adj[nod])
        {
            long long end=cost+u.cost;
            if(tip>0)
            {
                if(dp[u.unde][1][0]>end)
                {
                    dp[u.unde][1][0]=end;
                    pq.push({u.unde,end,2,0});
                }
            }
            else
            {
                if(dp[u.unde][0][0]>end)
                {
                    dp[u.unde][0][0]=end;
                    pq.push({u.unde,end,0,0});
                }

            }
        }

        if(tip<2)
        {
            for(auto u:pereche[nod])
            {
                if(drum==0)
                {
                    if(costuri[nod]<costuri[u])
                    {
                        if(dp[u][1][1]>dp[nod][tip][0])
                        {
                            dp[u][1][1]=dp[nod][tip][0];
                            pq.push({u,dp[u][1][1],1,1});
                        }
                    }
                    else
                    {
                        if(dp[u][1][2]>dp[nod][tip][0])
                        {
                            dp[u][1][2]=dp[nod][tip][0];
                            pq.push({u,dp[u][1][2],1,2});
                        }
                    }
                }
                else
                {
                    if(drum==1)
                    {
                        if(costuri[nod]<costuri[u])
                        {
                            if(dp[u][1][1]>dp[nod][1][1])
                            {
                                dp[u][1][1]=dp[nod][1][1];
                                pq.push({u,dp[u][1][1],1,1});
                            }
                        }
                    }
                    else if(costuri[nod]>costuri[u])
                    {
                        if(dp[u][1][2]>dp[nod][1][2])
                        {
                            dp[u][1][2]=dp[nod][1][2];
                            pq.push({u,dp[u][1][2],1,2});
                        }
                    }
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    cin>>casa>>scoala;
    cin>>mag1>>mag2;
    for(int i=1; i<=m; i++)
    {
        int nod1,nod2,cost;
        cin>>nod1>>nod2>>cost;
        adj[nod1].push_back({nod2,cost});
        adj[nod2].push_back({nod1,cost});
    }
    cauta_drum(casa);
    back_drum(scoala);
    calculeaza_cost(mag2);

    long long ans=infinit;
    for(int i=0; i<2; i++)
    {
        for(int k=0; k<=2; k++)
            ans=min(ans,dp[mag1][i][k]);
    }
    cout<<ans<<'\n';
    return 0;
}

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