Submission #814656

#	Time	Username	Problem	Language	Result	Execution time	Memory
814656		akari	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	402 ms	30584 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<ll,ll>
const ll maxn=2e5+2,inf=1e16;

int n,m,s,t,op,ed;
vector<ll> d1,d2,t1,t2;
vector<ii> adj[maxn];
vector<ll> g[maxn];
vector<int> ver;
bool ok[maxn];
bool pass[maxn];
ll ans=inf;
ll dp[maxn],pd[maxn];
int p[maxn];

void dij(int st, vector<ll> &dis){
    dis.resize(n+2,inf);
    priority_queue <ii,vector<ii>,greater<ii>> pq;
    pq.push({0,st});
    dis[st]=0;
    while(!pq.empty()){
        int u=pq.top().se;
        int d=pq.top().fi;
        pq.pop();
        if (dis[u]<d) continue;
        for (ii v:adj[u]){
            if (dis[v.fi]>dis[u]+v.se){
                if (st==s) p[v.fi]=u;
                dis[v.fi]=dis[u]+v.se;
                pq.push({dis[v.fi],v.fi});
            }
        }
    }
}

int main(){
    cin>>n>>m>>s>>t>>op>>ed;
    while (m--){
        int a,b,c; cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    dij(s,d1);
    dij(t,d2);
    dij(op,t1);
    dij(ed,t2);
    for (int i=1;i<=n;++i){
        dp[i]=t1[i];
        pd[i]=t2[i];
        if (d1[i]+d2[i] == d1[t]){
            ver.push_back(i);
            ok[i]=1;
        } 
    }
    if (s==op){
        for (int i:ver){
            ans=min(ans,t2[i]);
        }
        cout<<ans;
        return 0;
    }
    for (int i: ver){
        for (ii x: adj[i]) if (ok[x.fi]) g[i].push_back(x.fi);
    }
    /*ll sna=inf;
    for (int i:ver){
        ans=min(ans,t1[i]);
        sna=min(sna,t2[i]);
    }
    cout<<min(ans+sna,t1[ed]);
    /*queue<ii> qu;
    qu.push({s,s});
    pass[s]=1;
    while (!qu.empty()){
        int u=qu.front().fi;
        int p=qu.front().se;
        //cout<<u<<endl;
        qu.pop();
        dp[u]=min(dp[p],t2[u]);
        for (int v: g[u]){
            dp[v]=min(dp[u],t2[v]);
            if (pass[v]==0){
                pass[v]=1;
                qu.push({v,u});
            }
        }    
    }*/
    pass[s]=1;
    for (int i: ver){
        while (pass[i]==0){
            //cout<<i<<" ";
            pass[i]=1;
            dp[i]=min(dp[i],dp[p[i]]);
            pd[i]=min(pd[i],pd[p[i]]);
            i=p[i];
        }
        //cout<<i<<" i\n";
    }
    for (int u:ver) ans=min(ans,t2[u]+dp[u]);
    for (int v: ver) ans=min(ans,t1[v]+pd[v]);
    //for (int i:ver) cout<<i<<" "<<p[i]<<endl;  
    cout<<min(ans,t1[ed]);
}

Compilation message (stderr)

commuter_pass.cpp:75:5: warning: "/*" within comment [-Wcomment]
   75 |     /*queue<ii> qu;
      |

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