Submission #814741

#	Time	Username	Problem	Language	Result	Execution time	Memory
814741		akari	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	557 ms	32824 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=1e5+7,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+9,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){
                    g[v.fi].clear();
                }
                dis[v.fi]=dis[u]+v.se;
                pq.push({dis[v.fi],v.fi});
            }
            if (st==s&& dis[v.fi]>=d+v.se){
                p[v.fi]=u;
                g[v.fi].push_back(u);
            }
            
        }
    }
}

void dfs(int u){
    if (pass[u]) return;
    pass[u]=1;
    //cout<<u<<endl;
    for (int v: g[u]){
        dp[v]=min(dp[v],dp[u]);
        pd[v]=min(pd[v],pd[u]);
        dfs(v);
    }
}

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;
        } 
    }
    dfs(t);
    if (s==op){
        for (int i:ver){
            ans=min(ans,t2[i]);
        }
        cout<<ans;
        return 0;
    }
    /*ll sna=inf;
    for (int i:ver){
        ans=min(ans,t1[i]);
        sna=min(sna,t2[i]);
    }
    cout<<min(ans+sna,t1[ed]);
    return 0;*/
    /*for (int i: ver){
        for (ii x: adj[i]) if (ok[x.fi]) g[i].push_back(x.fi);
    }*/
    /*
    /*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 i: ver){
        for (int j: g[i]) cout<<j<<" "; cout<<i<<endl;
    }*/
    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:96:5: warning: "/*" within comment [-Wcomment]
   96 |     /*queue<ii> qu;
      |

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