Submission #367667

#	Time	Username	Problem	Language	Result	Execution time	Memory
367667		EIMONIM	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	605 ms	27428 KiB

commuter_pass

#include <bits/stdc++.h>
#define int int64_t
#define ii pair<int,int>
#define x first
#define y second
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<ii>
#define vvii vector<vii>
#define vb vector<bool>
#define vvb vector<vb>
#define pb push_back
#define loop(i,s,e) for(int i=(s);i<(e);i++)
#define loopr(i,s,e) for(int i=(e)-1;i>=(s);i--)
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
using namespace std;
const int INF = 2e18, MOD = 1e9 + 7;

int n,m;
vvii g;
vi dijkstra(int s){
    priority_queue<ii> q; q.push({0,s});
    vi d(n, INF); d[s] = 0;
    while(q.size()){
        int cur = q.top().y, dd = -q.top().x; q.pop();
        if (d[cur]!=dd) continue;
        for(auto nei:g[cur]){
            int v = dd + nei.y;
            if (v < d[nei.x]){
                d[nei.x] = v;
                q.push({-d[nei.x], nei.x});
            }
        }
    }
    return d;
}
int32_t main(){
    cin>>n>>m;
    int s,t; cin>>s>>t; s--, t--;
    int u,v; cin>>u>>v; u--, v--;
    g.resize(n);
    loop(i,0,m){
        int a,b,c; cin>>a>>b>>c;
        a--,b--;
        g[a].pb({b,c});
        g[b].pb({a,c});
    }
    vi ds = dijkstra(s), dt = dijkstra(t);
    vi du = dijkstra(u), dv = dijkstra(v);
    vb good(n);
    int d = ds[t];
    loop(i,0,n){
        int v = ds[i] + dt[i];
        if (v == d) good[i] = 1;
    }

    vvi ag(n);
    vi deg(n);
    loop(i,0,n) if(good[i]){
        for(auto nei:g[i]) if(good[nei.x]){
            int v = ds[i] + nei.y;
            if (v == ds[nei.x]){
                ag[nei.x].pb(i);
                deg[i]++;
            }
        }
    }
    queue<int> q;
    loop(i,0,n) if(deg[i]==0) q.push(i);
    vi bestu(n, INF), bestv(n, INF);
    int ans = du[v];
    while(q.size()){
        int cur = q.front(); q.pop();
        // cout<<"CUR: "<<cur+1<<endl;
        chkmin(ans, bestu[cur] + dv[cur]);
        chkmin(ans, bestv[cur] + du[cur]);

        chkmin(bestu[cur], du[cur]);
        chkmin(bestv[cur], dv[cur]);
        for(int nei:ag[cur]) {
            chkmin(bestu[nei], bestu[cur]);
            chkmin(bestv[nei], bestv[cur]);
            if (--deg[nei]==0) q.push(nei);
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*
color a
cls
g++ code.cpp -o code & code
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1

*/

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