Submission #45643

#	Time	Username	Problem	Language	Result	Execution time	Memory
45643		reality	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	735 ms	85764 KiB

commuter_pass

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = (int)(1e6) + 5;
ll D1[N];
ll D2[N];
ll D3[N];
ll D4[N];
vector < pii > g[N];
int n;
void Go(ll D[],int S) {
	for (int i = 1;i <= n;++i)
		D[i] = 1e18;
	D[S] = 0;
	priority_queue < pair < ll , int > , vector < pair < ll , int > > , greater < pair < ll , int > > > Q;
	Q.push(mp(0,S));
	while (!Q.empty()) {
		const ll cost = Q.top().fi;
		const int node = Q.top().se;
		Q.pop();
		if (cost != D[node])
			continue;
		for (auto it : g[node])
			if (D[it.fi] > D[node] + it.se)
				D[it.fi] = D[node] + it.se,Q.push(mp(D[it.fi],it.fi));
	}
}
ll ans = 1e18;
vi order;
vi G[2][N];
int was[N];
void go(ll d1[],ll d2[],int who) {
	static ll D[N];
	for (int i = 1;i <= n;++i)
		D[i] = d1[i];
	for (auto u : order)
		for (auto v : G[who][u])
			smin(D[u],D[v]);
	for (int i = 1;i <= n;++i)
		smin(ans,D[i] + d2[i]);
}
int main(void)
{
    int m;
    int S,T,U,V;
    cin>>n>>m>>S>>T>>U>>V;
    while (m --) {
    	int a,b,c;
    	cin>>a>>b>>c;
    	g[a].pb(mp(b,c));
    	g[b].pb(mp(a,c));
    }
    Go(D1,S);
    Go(D2,T);
    Go(D3,U);
    Go(D4,V);
    queue < int > q;
    q.push(S);
    was[S] = 1;
    const ll dist = D1[T];
    while (!q.empty()) {
    	int node = q.front();
    	q.pop();
    	order.pb(node);
    	for (auto it : g[node])
    		if (D1[node] + it.se + D2[it.fi] == dist) {
    			if (!was[it.fi])
	    			was[it.fi] = 1,q.push(it.fi);
    		}
    }
    for (int i = 1;i <= n;++i) {
    	for (auto it : g[i]) {
    		if (D1[i] + it.se + D2[it.fi] == dist)
    			G[0][i].pb(it.fi);
    		if (D1[it.fi] + it.se + D2[i] == dist)
    			G[1][it.fi].pb(i);
    	}
    }
    ans = D3[V];
    for (int cs = 0;cs < 2;++cs) {
	    go(D3,D4,cs);
	    go(D4,D3,cs);
	    reverse(all(order));
	    go(D3,D4,cs);
	    go(D4,D3,cs);
	    reverse(all(order));
	}
    cout << ans << '\n';
    return 0;
}

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