Submission #99542

#	Time	Username	Problem	Language	Result	Execution time	Memory
99542		mzhao	Commuter Pass (JOI18_commuter_pass)	C++11	24 / 100	253 ms	26476 KiB

commuter_pass

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

#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif

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

int N, M, S, T, U, V;
ll dis[303][303], ans = 1e16;
vector<pair<int, ll>> adj[100100];

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});
	}
	if (N <= 300) {
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				if (i != j) dis[i][j] = 1e16;
		for (int i = 1; i <= N; i++)
			for (pair<int, ll> j : adj[i])
				dis[i][j.x] = min(dis[i][j.x], j.y);
		for (int k = 1; k <= N; k++)
			for (int i = 1; i <= N; i++)
				for (int j = 1; j <= N; j++)
					dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				D("%lld ", dis[i][j]);
			}
			D("\n");
		}
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) if (i != j) {
				if (dis[S][i]+dis[i][j]+dis[j][T] == dis[S][T]) {
					D("valid %d %d = %lld\n", i, j, dis[U][i]+dis[j][V]);
					ans = min({ans, dis[U][i]+dis[j][V], dis[U][j]+dis[i][V]});
				}
			}
		}
		ans = min(ans, dis[U][V]);
	} else {
		assert(0);
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:19: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:21: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: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 45