Submission #727773

#	Time	Username	Problem	Language	Result	Execution time	Memory
727773		fdnfksd	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	517 ms	68656 KiB

commuter_pass

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,d[4][maxN];
bool vis[maxN];
vector<pli>g[maxN],adj[maxN],ke[maxN];
void dij(ll s,ll t)
{
    for(int i=1;i<=n;i++) d[t][i]=inf,vis[i]=false;
    d[t][s]=0;
    priority_queue<pli,vector<pli>,greater<pli>>pq;
    pq.push({d[t][s],s});
    while(!pq.empty())
    {
        ll u=pq.top().se;
        pq.pop();
        if(vis[u]==true) continue;
        vis[u]=true;
        for(auto vv:g[u])
        {
            ll v=vv.fi;
            ll w=vv.se;
            if(d[t][v]>d[t][u]+w)
            {
                d[t][v]=d[t][u]+w;
                pq.push({d[t][v],v});
            }
        }
    }
}
ll m,s,t,x,y;
struct qq
{
    ll u,v,w;

}a[maxN];
ll deg[maxN];
vector<ll>rev[maxN];ll dp1[maxN],dp2[maxN];
ll ans=inf;
void cal()
{
    for(int i=1;i<=n;i++) deg[i]=0,rev[i].clear(),dp1[i]=inf,dp2[i]=inf;
    for(int i=1;i<=n;i++)
    {
        for(auto zz:g[i])
        {
            deg[zz.fi]++;
            rev[zz.fi].pb(i);
        }
    }
    queue<int>q;
    for(int i=1;i<=n;i++) if(deg[i]==0) q.push(i);
    vector<ll> ver;
    while(!q.empty())
    {
        ll u=q.front();
        q.pop();
        ver.pb(u);
        for(auto zz:g[u])
        {
            deg[zz.fi]--;
            if(deg[zz.fi]==0) q.push(zz.fi);
        }
    }
    for(auto zz:ver)
    {
        dp1[zz]=d[2][zz];
        for(auto vv:rev[zz])
        {
            dp1[zz]=min(dp1[zz],dp1[vv]);
        }
        dp2[zz]=d[3][zz];
        for(auto vv:rev[zz])
        {
            dp2[zz]=min(dp2[zz],dp2[vv]);
        }
        ans=min(ans,dp1[zz]+d[3][zz]);
        ans=min(ans,dp2[zz]+d[2][zz]);
    }
}
void solve()
{
    cin >> n >> m;
    cin >> s >> t;
    cin >> x >> y;
    for(int i=1;i<=m;i++)
    {
        ll u,v,w;
        cin >> u >> v >> w;
        a[i].u=u;
        a[i].v=v;
        a[i].w=w;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    dij(s,0);
    dij(t,1);
    for(int i=1;i<=m;i++)
    {
        if(d[0][a[i].u]+d[1][a[i].v]+a[i].w==d[0][t])
        {
            adj[a[i].u].pb({a[i].v,0});
        }
        else if(d[0][a[i].v]+d[1][a[i].u]+a[i].w==d[0][t])
        {
            adj[a[i].v].pb({a[i].u,0});
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(d[0][a[i].u]+d[1][a[i].v]+a[i].w==d[0][t])
        {
            ke[a[i].v].pb({a[i].u,0});
        }
        else if(d[0][a[i].v]+d[1][a[i].u]+a[i].w==d[0][t])
        {
            ke[a[i].u].pb({a[i].v,0});
        }
    }
    dij(x,2);
    dij(y,3);
    for(int i=1;i<=n;i++) swap(adj[i],g[i]);
    cal();
    for(int i=1;i<=n;i++) swap(ke[i],g[i]);
    cal();
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

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