Submission #548153

#	Time	Username	Problem	Language	Result	Execution time	Memory
548153		AA_Surely	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	430 ms	51800 KiB

commuter_pass

#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int N = 2e5 + 7;
const int ALPHA = 27;
const LL INF = 1e18;
const int MOD = 1e9 + 7;
const int LOG = 22;

LL n, m, s, t, u, v;
LL deg[N], rm[N];
bool colored[N];

LL dist[N], sdist[N], udist[N], vdist[N];
LL mnu[N], mnv[N];

VPLL adj[N];
VLL dag[N], par[N], order, rdag[N];

void sdijk() {
    fill(sdist, sdist + n, INF);
    
    sdist[s] = 0;
    priority_queue<PLL> keep;
    keep.push({0, s});

    while(!keep.empty()) {
        int now = keep.top().S;

        keep.pop();

        for(auto [on, w] : adj[now]) {
            if (sdist[on] > sdist[now] + w) {
                sdist[on] = sdist[now] + w;

                keep.push({-sdist[on], on});
            }

        }
    }

    F0R(i, n) for(auto [on, w] : adj[i]) 
        if (sdist[on] + w == sdist[i]) par[i].pb(on);
    

    return;
}

void odijk(int sc) {
    fill(dist, dist + n, INF);
    dist[sc] = 0;

    priority_queue<PLL> keep;
    keep.push({0, sc});

    while(!keep.empty()) {
        int now = keep.top().S;
        keep.pop();

        for(auto [on, w] : adj[now]) if (dist[on] > dist[now] + w) {
            dist[on] = dist[now] + w;
            keep.push({-dist[on], on});
        }
    }

    return;
}

void clarify() {
    F0R(i, n) for(int on : par[i])
        deg[on]++;
    
    queue<int> dl;
    F0R(i, n) if (!deg[i] && i != t) 
        dl.push(i);
        
    while(!dl.empty()) {
        int now = dl.front();
        dl.pop();

        for(int on : par[now]) {
            deg[on]--;
            if (!deg[on] && on != t) dl.push(on);
        }

        rm[now] = 1;
    }

    F0R(i, n) if (!rm[i]) for(int on : par[i]) {
        if (!rm[on]) {
            dag[on].pb(i);
            rdag[i].pb(on);
        }
    }

    return;
}

void dfs(int now) {
    colored[now] = 1;
    for(int on : dag[now]) if (!colored[on]) 
        dfs(on);

    order.pb(now);
    return;
}

int main() {
    IOS;
    
    cin >> n >> m >> s >> t >> u >> v;
    s--; t--; v--; u--;

    F0R(i, m) {
        LL a, b, w; cin >> a >> b >> w;
        adj[--a].pb({--b, w});
        adj[b].pb({a, w});
    }

    sdijk();

    odijk(u);
    F0R(i, n) udist[i] = dist[i];

    odijk(v);
    F0R(i, n) vdist[i] = dist[i];

    clarify();

    dfs(s);
    reverse(ALL(order));

    fill(mnu, mnu + n, INF);
    fill(mnv, mnv + n, INF);

    LL ans = INF;

    for(int now : order) {
        for(int on : rdag[now]) {
            mnu[now] = min(mnu[now], mnu[on]);
            mnv[now] = min(mnv[now], mnv[on]);
        }

        mnu[now] = min(mnu[now], udist[now]);
        mnv[now] = min(mnv[now], vdist[now]);

        ans = min({ans, udist[now] + mnv[now], vdist[now] + mnu[now]});
    }

    ans = min(ans, udist[v]);

    cout << ans;
}

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