Submission #48475

#	Time	Username	Problem	Language	Result	Execution time	Memory
48475		kyleliu	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	614 ms	48796 KiB

commuter_pass

#include <bits/stdc++.h> // PLEASE

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pp;
#define MAXN 300005
#define MAXM 1005
#define MAXP 25
#define A first
#define B second
#define MP make_pair
#define PB push_back
const ll INF = 2e9+13;
const ll MOD = 1e9+7;
int N, M;
int S[4]; // S T U V
vector <pp> g[MAXN];
ll d[4][MAXN];
ll dp[2][MAXN];
bool vis[MAXN];

void run(int i) {
	priority_queue <pp> PQ;
	memset(vis, 0, sizeof(vis));
	PQ.push({0, S[i]});
	while(!PQ.empty()) {
		ll di = -PQ.top().A;
		int u = PQ.top().B;
		PQ.pop();
		if(vis[u]) continue;
		vis[u] = 1; d[i][u] = di;
		for(auto e : g[u]) if(!vis[e.A]) PQ.push({-1LL*(di + e.B), e.A});
		
	}
}

void run2(int i) {
	priority_queue <pp> PQ;
	memset(vis, 0, sizeof(vis));
	PQ.push({0, S[i]});
	while(!PQ.empty()) {
		ll di = -PQ.top().A;
		int u = PQ.top().B;
		PQ.pop();
		if(vis[u]) continue;
		dp[i][u] = min(dp[i][u], d[2][u]);
		vis[u] = 1; d[i][u] = di;
		for(auto e : g[u]) if(!vis[e.A]) if(di + e.B == d[i][e.A]) { // shortest path
			PQ.push({-1LL*(di + e.B), e.A});
			dp[i][e.A] = min(dp[i][e.A], dp[i][u]);
		}	
	}
}
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for(int i=0; i<4; i++) cin >> S[i];
	for(int i=0; i<M; i++) {
		int a, b; ll c;
		cin >> a >> b >> c;
		g[a].PB({b, c});
		g[b].PB({a, c});
	}
	for(int i=0; i<4; i++) run(i);
	for(int i=0; i<2; i++) for(int j=1; j<=N; j++) dp[i][j] = 1e18;
	for(int i=0; i<2; i++) run2(i);
	ll ans = d[2][S[3]];
	ll sp = d[0][S[1]];
	for(int i=1; i<=N; i++) 
		if(d[0][i] + d[1][i] == sp) {
			ans = min(ans, d[3][i] + min(dp[0][i], dp[1][i]));
		}
	cout << ans << endl;
	
}

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