Submission #99460

#	Time	Username	Problem	Language	Result	Execution time	Memory
99460		mzhao	Commuter Pass (JOI18_commuter_pass)	C++11	31 / 100	608 ms	38892 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

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

ll dist[100100][10];
ll par[100100][10];
bool vis[100100];

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

void dfs(ll n) {
	if (!n || vis[n]) return;
	D("at %d\n", n);
	vis[n] = 1;
	ans = min(ans, dist[n][1]);
	for (ll i : nadj[n]) dfs(i);
}

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 (S == U) {
		dij(S, 0);
		dij(V, 1);
		for (int i = 1; i <= N; i++) D("%lld ", dist[i][0]);
		D("\n");
		for (int i = 1; i <= N; i++) D("%lld ", dist[i][1]);
		D("\n");
		for (int i = 1; i <= N; i++) vis[i] = 0;
		dfs(T);
	} else {
		dij(S, 0);
		for (int i = T; i != S;) {
			assert(nadj[i].size() == 1);
			ll prv = nadj[i][0];
			for (int j = 0; j < adj[prv].size(); j++) {
				if (adj[prv][j].x == i) {
					adj[prv][j].y = 0;
					break;
				}
			}
			for (int j = 0; j < adj[i].size(); j++) {
				if (adj[i][j].x == prv) {
					adj[i][j].y = 0;
					break;
				}
			}
			i = prv;
		}
		for (int i = 1; i <= N; i++) {
			D("%d = ", i);
			for (pair<ll, ll> j : adj[i]) D("(%lld, %lld) ", j.x, j.y);
			D("\n");
		}
		dij(V, 1);
		for (int i = 1; i <= N; i++) D("%lld ", dist[i][0]);
		D("\n");
		for (int i = 1; i <= N; i++) D("%lld ", dist[i][1]);
		D("\n");
		ans = dist[U][1];
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:53:46: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  scanf("%d%d%d%d%d%d", &N, &M, &S, &T, &U, &V);
                        ~~                    ^
commuter_pass.cpp:53:46: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
commuter_pass.cpp:53:46: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
commuter_pass.cpp:53:46: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'long long int*' [-Wformat=]
commuter_pass.cpp:53:46: warning: format '%d' expects argument of type 'int*', but argument 6 has type 'long long int*' [-Wformat=]
commuter_pass.cpp:53:46: warning: format '%d' expects argument of type 'int*', but argument 7 has type 'long long int*' [-Wformat=]
commuter_pass.cpp:73:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < adj[prv].size(); j++) {
                    ~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < adj[i].size(); j++) {
                    ~~^~~~~~~~~~~~~~~
commuter_pass.cpp:89:22: warning: variable 'j' set but not used [-Wunused-but-set-variable]
    for (pair<ll, ll> j : adj[i]) D("(%lld, %lld) ", j.x, j.y);
                      ^
commuter_pass.cpp:53: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:55: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