Submission #99590

#	Time	Username	Problem	Language	Result	Execution time	Memory
99590		mzhao	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	789 ms	33380 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 = 0; i < 4; i++)
		for (int j = 1; j <= N; j++)
			best[i][j] = 1e16;
	for (int _ = 0; _ < 2; _++) {
		for (int i : v) {
			for (int k = 2*_; k < 2*_+2; k++) {
				best[k][i] = dis[(k&1)+1][i];
				for (int j : prv[i]) {
					best[k][i] = min(best[k][i], best[k][j]);
				}
			}
		}
		reverse(v.begin(), v.end());
	}
	ll ans = dis[1][V];
	for (int i = 1; i <= N; i++) {
		ans = min({ans, best[0][i]+best[3][i], best[1][i]+best[2][i]});
	}
	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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 }
 ^
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:45:5: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 int main() {
     ^~~~
commuter_pass.cpp:45:5: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:45:5: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]

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