Submission #1067245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067245		sitablechair	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	225 ms	63688 KiB

commuter_pass

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define REP(i,l,r) For(i,l,r-1)
#define PER(i,r,l) ForD(i,r-1,l)
#define ff first
#define ss second
#define pb emplace_back
#define all(x) x.begin(),x.end()
#define All(x,n) x+1,x+1+n
#define Alll(x,n) x,x+n
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define mpa make_pair

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=4e5+9;
const ll INF=1e17;
struct edge {
    int u,v,w;
    edge(int k=0,int x=0,int y=0): u(k),v(x),w(y) {};
};

int n,m,a,b,c,d;
vector<edge> g[N],g1[N],g2[N];
vector<int> topo;
edge ed[N];
ll dis[N],dis1[N],f[N];
bool vs[N];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
void dijkstra(int u,ll *out) {
    fill(out,out+n+1,INF);
    out[u]=0;
    pq.push(mpa(0,u));
    while(sz(pq)) {
        ll w=pq.top().ff;
        int cu=pq.top().ss;
        pq.pop();
        for(auto v: g[cu]) {
            if (out[v.v]>v.w+w) {
                out[v.v]=v.w+w;
                pq.push(mpa(out[v.v],v.v));
            } 
        }
    }
}
void dfs(int u) {
    vs[u]=1;
    for(auto v: g1[u]) if (!vs[v.v]) dfs(v.v);
    topo.pb(u);
}
ll solve() {
    ll ans=1e17;
    fill(f,f+n+2,INF);
    for(auto u: topo) {
        f[u]=dis[u];
        for(auto v: g2[u]) f[u]=min(f[u],f[v.v]);
        ans=min(ans,f[u]+dis1[u]);
    }
    return ans;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> a >> b >> c >> d;
    For(i,1,m) {
        int u,v,w;
        cin >> u >> v >> w;
        ed[i]=edge(u,v,w);
        g[u].pb(edge(u,v,w));
        g[v].pb(edge(v,u,w));
    }
    dijkstra(a,dis);
    dijkstra(b,dis1);
    For(i,1,m) {
        if (dis[ed[i].u]+dis1[ed[i].v]+ed[i].w==dis[b]) {
            g1[ed[i].u].pb(ed[i]);
            g2[ed[i].v].pb(edge(ed[i].v,ed[i].u,ed[i].w));
        }
        if (dis[ed[i].v]+dis1[ed[i].u]+ed[i].w==dis[b]) {
            g1[ed[i].v].pb(edge(ed[i].v,ed[i].u,ed[i].w));
            g2[ed[i].u].pb(ed[i]);
        }
    }
    dijkstra(c,dis);
    dijkstra(d,dis1);
    For(i,1,n) if (!vs[i]) dfs(i);
    reverse(all(topo));
    ll res=dis[d];
    res=min(res,solve());
    swap(dis,dis1);
    res=min(res,solve());
    cout << res;
    return 0;
}

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