Submission #561125

#	Time	Username	Problem	Language	Result	Execution time	Memory
561125		Zanite	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	360 ms	29288 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define fi first
#define se second
using namespace std;

const ll maxN = 1e5 + 5, INF = 1e18;
ll N, M, S, T, U, V, pred[maxN];
vector<ll> dist;
set<pll> zero;
vector<pll> adj[maxN];
bool vis[maxN];

void dijkstra(ll start) {
	priority_queue<pll, vector<pll>, greater<pll> > PQ;
	dist.clear();
	dist.assign(N+1, INF);
	PQ.push({0, start});
	dist[start] = 0;
	pred[start] = -1;
	memset(vis, 0, sizeof(vis));

	while (!PQ.empty()) {
		ll cdist = PQ.top().fi;
		ll cur = PQ.top().se;
		PQ.pop();
		if (vis[cur]) continue;

		vis[cur] = 1;
		for (auto i : adj[cur]) {
			ll weight = i.se;
			if (zero.count({cur, i.fi})) weight = 0;

			if (dist[i.fi] > dist[cur] + weight) {
				dist[i.fi] = dist[cur] + weight;
				pred[i.fi] = cur;
				PQ.push({dist[i.fi], i.fi});
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> N >> M >> S >> T >> U >> V;
	for (ll A, B, C, i = 1; i <= M; i++) {
		cin >> A >> B >> C;
		adj[A].push_back({B, C});
		adj[B].push_back({A, C});
	}

	dijkstra(S);

	/*
	for (ll i = 1; i <= N; i++) {
		cout << i << " " << dist[i] << " " << pred[i] << '\n';
	}
	*/

	ll cur = T, pre = pred[T];
	while (pre != -1) {
		zero.insert({cur, pre});
		zero.insert({pre, cur});
		cur = pre;
		pre = pred[pre];
	}

	dijkstra(U);
	cout << dist[V] << '\n';
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(long long int)':
commuter_pass.cpp:25:6: warning: unused variable 'cdist' [-Wunused-variable]
   25 |   ll cdist = PQ.top().fi;
      |      ^~~~~

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