Submission #99582

#	Time	Username	Problem	Language	Result	Execution time	Memory
99582		mzhao	Commuter Pass (JOI18_commuter_pass)	C++11	31 / 100	705 ms	33332 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define MX 100100
#define ll long long
#define x first
#define y second

int N, M, S, T, U, V;
ll dis[3][MX], best[4][MX];
bool vis[MX];

vector<pair<int, int>> adj[MX];
vector<int> par[MX], nxt[MX], prv[MX], v;

void dij(int s, int z) {
	priority_queue<pair<ll, pair<int, int>>> q;
	q.push({0, {s, 0}});
	while (q.size()) {
		pair<ll, pair<int, int>> cur = q.top(); q.pop();
		if (!z && cur.y.y && (!vis[cur.y.x] || dis[z][cur.y.x] == -cur.x)) {
			par[cur.y.x].push_back(cur.y.y);
		}
		if (vis[cur.y.x]) continue;
		vis[cur.y.x] = 1;
		dis[z][cur.y.x] = -cur.x;
		for (pair<int, int> i : adj[cur.y.x]) {
			q.push({cur.x-i.y, {i.x, cur.y.x}});
		}
	}
	for (int i = 1; i <= N; i++) vis[i] = 0;
}

void dfs(int n) {
	if (vis[n]) return;
	vis[n] = 1;
	for (int i : par[n]) {
		nxt[i].push_back(n);
		prv[n].push_back(i);
		dfs(i);
	}
	v.push_back(n);
}

int main() {
	scanf("%d%d%d%d%d%d", &N, &M, &S, &T, &U, &V);
	for (int i = 0, A, B, C; i < M; i++) {
		scanf("%d%d%d", &A, &B, &C);
		adj[A].push_back({B, C});
		adj[B].push_back({A, C});
	}
	dij(S, 0); dij(U, 1); dij(V, 2);
	dfs(T);
	for (int i : v) {
		for (int k = 0; k < 2; k++) {
			best[k][i] = dis[k+1][i];
			for (int j : prv[i]) {
				best[k][i] = min(best[k][i], best[k][j]);
			}
		}
	}
	reverse(v.begin(), v.end());
	for (int i : v) {
		for (int k = 2; k < 4; k++) {
			best[k][i] = dis[k-1][i];
			for (int j : nxt[i]) {
				best[k][i] = min(best[k][i], best[k][j]);
			}
		}
	}
	ll ans = dis[1][V];
	for (int i = T;; i = prv[i][0]) {
		ans = min({ans, best[0][i]+best[3][i], best[1][i]+best[2][i]});
		if (i == S) break;
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d%d", &N, &M, &S, &T, &U, &V);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &A, &B, &C);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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