Submission #814779

#	Time	Username	Problem	Language	Result	Execution time	Memory
814779		akari	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	362 ms	27084 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){
                dis[v.fi]=dis[u]+v.se;
                pq.push({dis[v.fi],v.fi});
            }        
        }
    }
}

void dfs(int u){
    if (pass[u]) return;
    pass[u]=1;
    //cout<<u<<endl;
    for (ii i: adj[u]){
        int v=i.fi;
        if (ok[v]==0) continue;
        if (d1[u]+d2[v]+i.se==d1[t]){
            //cout<<u<<" "<<v<<endl;
            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<int> qu;
    qu.push(s);
    while (!q.empty()){

    }*/
    /*pass[s]=1;
    for (int i: ver){
        while (pass[i]==0){
            //cout<<i<<" ";
            for (int v: g[i]){
                if (!ok[v]) continue;
                dp[i]=min(dp[i],dp[v]);
                pd[i]=min(pd[i],pd[v]);
            }
            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;
    }*/
    dfs(s);
    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:114:5: warning: "/*" within comment [-Wcomment]
  114 |     /*for (int i: ver){
      |

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