Submission #370931

#	Time	Username	Problem	Language	Result	Execution time	Memory
370931		Fysty	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	661 ms	31456 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
const ll INF=2e18;
vector<pll> ed[100005];
ll dist[100005][5],ds[100005],dt[100005],dv[100005];
ll s,t;
void dijk(ll n)
{
    priority_queue<pair<ll,pll>,vector<pair<ll,pll> >,greater<pair<ll,pll> > > pq;
    pq.push({0,{n,0}});
    dist[n][0]=0;
    while(!pq.empty())
    {
        auto p=pq.top();pq.pop();
        ll d=p.F,u=p.S.F,x=p.S.S;
        if(dist[u][x]<d) continue;
        for(auto tmp:ed[u])
        {
            ll v=tmp.F,len=tmp.S;
            if(x==0)
            {
                if(dist[v][0]>d+len)
                {
                    dist[v][0]=d+len;
                    pq.push({d+len,{v,0}});
                }
                if(ds[u]+dt[v]+len==ds[t])
                {
                    if(dist[v][1]>d)
                    {
                        dist[v][1]=d;
                        pq.push({d,{v,1}});
                    }
                }
                if(ds[v]+dt[u]+len==ds[t])
                {
                    if(dist[v][3]>d)
                    {
                        dist[v][3]=d;
                        pq.push({d,{v,3}});
                    }
                }
            }
            else if(x==1)
            {
                if(dist[v][2]>d+len)
                {
                    dist[v][2]=d+len;
                    pq.push({d+len,{v,2}});
                }
                if(ds[u]+dt[v]+len==ds[t])
                {
                    if(dist[v][1]>d)
                    {
                        dist[v][1]=d;
                        pq.push({d,{v,1}});
                    }
                }
            }
            else if(x==3)
            {
                if(dist[v][2]>d+len)
                {
                    dist[v][2]=d+len;
                    pq.push({d+len,{v,2}});
                }
                if(ds[v]+dt[u]+len==ds[t])
                {
                    if(dist[v][3]>d)
                    {
                        dist[v][3]=d;
                        pq.push({d,{v,3}});
                    }
                }
            }
            else
            {
                if(dist[v][2]>d+len)
                {
                    dist[v][2]=d+len;
                    pq.push({d+len,{v,2}});
                }
            }
        }
    }
}
int main()
{
    int n,m,a,b;
    cin>>n>>m>>s>>t>>a>>b;
    rep(i,m)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        ed[u].pb({v,w});
        ed[v].pb({u,w});
    }
    rep1(i,n) ds[i]=dt[i]=INF;
    rep1(i,n) rep(j,5) dist[i][j]=INF;
    priority_queue<pll,vector<pll>,greater<pll> > pq;
    pq.push({0,s});
    ds[s]=0;
    while(!pq.empty())
    {
        ll d=pq.top().F,u=pq.top().S;pq.pop();
        if(d>ds[u]) continue;
        for(auto v:ed[u])
        {
            if(ds[v.F]<=v.S+d) continue;
            ds[v.F]=v.S+d;
            pq.push({ds[v.F],v.F});
        }
    }
    pq.push({0,t});
    dt[t]=0;
    while(!pq.empty())
    {
        ll d=pq.top().F,u=pq.top().S;pq.pop();
        if(d>dt[u]) continue;
        for(auto v:ed[u])
        {
            if(dt[v.F]<=v.S+d) continue;
            dt[v.F]=v.S+d;
            pq.push({dt[v.F],v.F});
        }
    }
    dijk(a);
    cout<<min({dist[b][0],dist[b][1],dist[b][2],dist[b][3]});
}

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