Submission #1116744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116744		onlk97	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	343 ms	34216 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back
using namespace std;
using pii=pair <int,int>;
using tii=pair <pii,int>;
int n,m;
vector <pii> g[100010];
vector <int> gg[100010];
bool visited[100010];
vector <int> getdist(int s){
    vector <int> dist(n+1,1e18);
    dist[s]=0;
    for (int i=1; i<=n; i++) visited[i]=0;
    priority_queue <pii,vector <pii>,greater <pii> > pq;
    pq.push({0,s});
    while (!pq.empty()){
        pii tp=pq.top(); pq.pop();
        if (visited[tp.y]) continue;
        visited[tp.y]=1;
        for (pii i:g[tp.y]){
            if (!visited[i.x]&&tp.x+i.y<dist[i.x]){
                dist[i.x]=tp.x+i.y;
                pq.push({dist[i.x],i.x});
            }
        }
    }
    return dist;
}
vector <int> topo;
void dfs(int cur){
    visited[cur]=1;
    for (int i:gg[cur]){
        if (!visited[i]) dfs(i);
    }
    topo.pb(cur);
}
void solve(){
    int s,t,u,v;
    cin>>n>>m>>s>>t>>u>>v;
    tii edg[m+1];
    for (int i=1; i<=m; i++){
        cin>>edg[i].x.x>>edg[i].x.y>>edg[i].y;
        g[edg[i].x.x].pb({edg[i].x.y,edg[i].y});
        g[edg[i].x.y].pb({edg[i].x.x,edg[i].y});
    }
    vector <int> ds=getdist(s),dt=getdist(t),du=getdist(u),dv=getdist(v);
    for (int i=1; i<=m; i++){
        if (ds[edg[i].x.x]+edg[i].y+dt[edg[i].x.y]==ds[t]){
            gg[edg[i].x.x].pb(edg[i].x.y);
        } else if (ds[edg[i].x.y]+edg[i].y+dt[edg[i].x.x]==ds[t]){
            gg[edg[i].x.y].pb(edg[i].x.x);
        }
    }
    for (int i=1; i<=n; i++) visited[i]=0;
    for (int i=1; i<=n; i++){
        if (!visited[i]) dfs(i);
    }
    reverse(topo.begin(),topo.end());
    bool ok[n+1];
    for (int i=1; i<=n; i++) ok[i]=(i==s);
    int ans=du[v];
    for (int i:topo){
        if (!ok[i]) continue;
        for (int j:gg[i]){
            ok[j]=1;
            du[j]=min(du[j],du[i]);
        }
        ans=min(ans,du[i]+dv[i]);
    }
    for (int i=1; i<=n; i++) ok[i]=(i==s);
    du=getdist(v); dv=getdist(u);
    for (int i:topo){
        if (!ok[i]) continue;
        for (int j:gg[i]){
            ok[j]=1;
            du[j]=min(du[j],du[i]);
        }
        ans=min(ans,du[i]+dv[i]);
    }
    cout<<ans<<'\n';
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
}

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