Submission #728547

#	Time	Username	Problem	Language	Result	Execution time	Memory
728547		beaboss	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	465 ms	29048 KiB

commuter_pass

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;

const ll INF = 1e17 + 10ll;

int main() {
	
	
	ll n, m;
	cin >> n >> m;

	ll s, t;
	cin >> s >> t;

	ll u, v;
	cin >> u >> v;

	

	
	u--;v--;s--;t--;

	vector<vector<pii> > adj(n);

	for (ll i = 0; i < m; i++) {
		ll a,b,w;
		cin >> a >> b >> w;
		adj[--a].push_back({--b, w});
		adj[b].push_back({a, w});
	}

	vector<ll> distu(n, -1);
	vector<ll> distv(n, -1);


	// distu[u]=0;
	// distv[v]=0;



	priority_queue<pii> q;

	q.push({0, u});
	while (!q.empty()) {
		ll cur = q.top().s;
		ll dist = q.top().f;
		q.pop();

		if (distu[cur] >= 0ll) continue;
		distu[cur] = -dist;
		// cout << cur << endl;
		for (auto val: adj[cur]) {
			if (distu[val.f] == -1ll) {
				q.push({-distu[cur] - val.s, val.f});
			}
		}
	}


	q.push({0, v});
	while (!q.empty()) {
		ll cur = q.top().s;
		ll dist = q.top().f;
		q.pop();

		if (distv[cur] >= 0ll) continue;
		distv[cur] = -dist;
		// cout << cur << endl;
		for (auto val: adj[cur]) {
			if (distv[val.f] == -1ll) {
				q.push({-distv[cur] - val.s, val.f});
			}
		}
	}

	vector<ll> minans(n, INF);

	vector<ll> minprev(n, INF);

	vector<ll> minans1(n, INF);

	vector<ll> minprev1(n, INF);
	vector<ll> dist(n, -1);

	priority_queue<pair<ll, pii> > bq;

	for (auto val: adj[s]) bq.push({-val.s, {val.f, s}});
	
	dist[s]=0;

	minprev[s] = distu[s];
	minans[s] = distu[v];

	minprev1[s] = distv[s];
	minans1[s] = distv[u];

	assert(distu[v]==distv[u]);


	while (!bq.empty()) {
		ll cur = bq.top().s.f;
		ll prev = bq.top().s.s;
		ll d = bq.top().f;
		bq.pop();

		if (-d > dist[cur] && dist[cur]!=-1) continue;
		bool prevdone = (dist[cur] != -1);
		assert(dist[cur] == -1 || dist[cur]==-d);

		dist[cur] = -d;
		minprev[cur] = min(min(minprev[prev], distu[cur]), minprev[cur]);
		minans[cur] = min(min(minans[prev], minprev[cur] + distv[cur]), minans[cur]);

		minprev1[cur] = min(min(minprev1[prev], distv[cur]), minprev1[cur]);
		minans1[cur] = min(min(minans1[prev], minprev1[cur] + distu[cur]), minans1[cur]);
		// cout << cur << minprev[cur] << endl;
		if (prevdone) continue;
		for (auto val: adj[cur]) {
			if (dist[val.f] == -1) {
				
				bq.push({-dist[cur] - val.s, {val.f, cur}});
			}
		}
	}

	cout << min(minans[t], minans1[t]) << endl;





	
	
}

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