Submission #99458

#	Time	Username	Problem	Language	Result	Execution time	Memory
99458		mzhao	Commuter Pass (JOI18_commuter_pass)	C++11	16 / 100	580 ms	31476 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;
vector<pair<int, int>> adj[100100];
vector<int> nadj[100100];
ll ans = 1e16;

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

void dij(int s, int z) {
	priority_queue<pair<ll, pair<int, int>>> 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<int, int>> 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<int, int> i : adj[cur.y.x]) {
			q.push({cur.x-i.y, {i.x, cur.y.x}});
		}
	}
}

void dfs(int n) {
	if (!n || vis[n]) return;
	D("at %d\n", n);
	vis[n] = 1;
	ans = min(ans, dist[n][1]);
	for (int 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);
			int 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;
				}
			}
			i = prv;
		}
		dij(U, 1);
		ans = dist[V][1];
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

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