Submission #561126

#	Time	Username	Problem	Language	Result	Execution time	Memory
561126		Zanite	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	410 ms	28500 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define fi first
#define se second
using namespace std;

const short int S = 0, T = 1, U = 2, V = 3;
const ll maxN = 1e5 + 5, INF = 1e18;
ll N, M, node[4], dist[4][maxN], memo[maxN][2];
vector<ll> pred[maxN];
vector<pll> adj[maxN];
bool vis[maxN], mark[maxN];

void dijkstra(ll idx, ll start) {
	priority_queue<pll, vector<pll>, greater<pll> > PQ;
	for (ll i = 1; i <= N; i++) {
		dist[idx][i] = INF;
	}

	PQ.push({0, start});
	dist[idx][start] = 0;
	memset(vis, 0, sizeof(vis));

	while (!PQ.empty()) {
		ll cdist = PQ.top().fi;
		ll cur = PQ.top().se;
		PQ.pop();
		if (vis[cur]) continue;

		vis[cur] = 1;
		for (auto i : adj[cur]) {
			ll weight = i.se;
			if (dist[idx][i.fi] > dist[idx][cur] + weight) {
				dist[idx][i.fi] = dist[idx][cur] + weight;
				if (idx == S) {pred[i.fi].push_back(cur);}
				PQ.push({dist[idx][i.fi], i.fi});
			}
		}
	}
}

ll dp(ll idx, bool type) {
	//cout << idx << " " << type << '\n';
	if (idx == node[V]) return 0;
	if (memo[idx][type] != -1) return memo[idx][type];

	ll ret = dist[V][idx];
	//cout << "here\n";

	for (auto a : adj[idx]) {
		ll nxt = a.fi, weight = a.se;
		//cout << nxt << '\n';

		if (type) {
			// S to T
			if (dist[S][idx] + weight + dist[T][nxt] == dist[S][node[T]]) {
				ret = min(ret, dp(nxt, 1));
			}
		} else {
			// T to S
			if (dist[T][idx] + weight + dist[S][nxt] == dist[T][node[S]]) {
				ret = min(ret, dp(nxt, 0));
			}
		}
	}

	return memo[idx][type] = ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> N >> M >> node[S] >> node[T] >> node[U] >> node[V];
	for (ll A, B, C, i = 1; i <= M; i++) {
		cin >> A >> B >> C;
		adj[A].push_back({B, C});
		adj[B].push_back({A, C});
	}

	dijkstra(S, node[S]);
	dijkstra(T, node[T]);
	dijkstra(U, node[U]);
	dijkstra(V, node[V]);

	/*
	for (ll i = 1; i <= N; i++) {
		for (ll j = 0; j < 4; j++) {
			cout << dist[j][i] << " ";
		}
		cout << '\n';
	}
	*/

	/*
	// mark all nodes in the shortest routes from S to T
	queue<ll> Q;
	Q.push(node[T]);
	while (!Q.empty()) {
		ll cur = Q.front();
		Q.pop();
		if (mark[cur]) continue;

		mark[cur] = 1;
		for (auto i : pred[cur]){
			Q.push(i);
		}
	}

	for (ll i = 1; i <= N; i++) {
		if (mark[i]) cout << i << " ";
	}
	cout << '\n';
	*/

	memset(memo, -1, sizeof(memo));

	ll ans = dist[V][node[U]];
	for (ll i = 1; i <= N; i++) {
		if (dist[S][i] + dist[T][i] == dist[S][node[T]]) {
			// i is on one of the shortest paths from S to T
			ans = min(ans, dist[U][i] + min(dp(i, 0), dp(i, 1)));
		}
	}

	cout << ans << '\n';
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(long long int, long long int)':
commuter_pass.cpp:26:6: warning: unused variable 'cdist' [-Wunused-variable]
   26 |   ll cdist = PQ.top().fi;
      |      ^~~~~

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