제출 #1095970

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1095970		I_FloPPed21	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2057 ms	19148 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];
struct drum
{
    int unde,cost;
};
struct coada
{
    int nod;
    long long cost;
    int a_folosit;//asta e de 3 tipuri
};

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

void reset()
{
    for(int i=1;i<=n;i++)
        {costuri[i]=infinit;
        dp[i][0]=infinit;
        dp[i][1]=infinit;}
}
vector<drum>adj[N];
void cauta_drum(int start)
{
    priority_queue<coada,vector<coada>,compara>pq;
    reset();
    costuri[start]=0;
    coada x={start,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();
        long long mn=costuri[nod];
        for(auto u:adj[nod])
        {
            mn=min(mn,costuri[u.unde]);
        }
        if(mn==costuri[nod])
            continue;

        for(auto u:adj[nod])
        {
            if(costuri[u.unde]==mn)
            {
                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;
    pq.push({start,0,0});
    while(!pq.empty())
    {
        int nod,tip;
        long long cost;
        nod=pq.top().nod;
        cost=pq.top().cost;
        tip=pq.top().a_folosit;
        pq.pop();
        for(auto u:adj[nod])
        {
            long long end=cost+u.cost;
            if(tip>0)
            {
                if(dp[u.unde][1]>end)
                {
                    dp[u.unde][1]=end;
                    pq.push({u.unde,end,2});
                }
            }
            else
            {
                if(dp[u.unde][0]>end)
                {
                    dp[u.unde][0]=end;
                    pq.push({u.unde,end,0});
                }

            }
        }

        if(tip<2)
        {
            for(auto u:pereche[nod])
            {
                if(dp[u][1]>dp[nod][tip])
                {
                    dp[u][1]=dp[nod][tip];
                    pq.push({u,dp[u][1],1});
                }
            }
        }
    }
}
int main()
{
    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);
    cout<<min(dp[mag1][0],dp[mag1][1])<<'\n';
    return 0;
}

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