Submission #728527

#	Time	Username	Problem	Language	Result	Execution time	Memory
728527		beaboss	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	481 ms	28756 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 = 1e9 + 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);

	vector<bool> uvis(n, false);
	vector<bool> tvis(n, false);


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

	vector<ll> minans(n, -1);

	vector<ll> minprev(n, -1);

	vector<ll> minans1(n, -1);

	vector<ll> minprev1(n, -1);
	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]);

	ll ans = 0;

	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);
		dist[cur] = -d;
		minprev[cur] = min(minprev[prev], distu[cur]);
		minans[cur] = min(minans[prev], minprev[cur] + distv[cur]);

		minprev1[cur] = min(minprev1[prev], distv[cur]);
		minans1[cur] = min(minans1[prev], minprev1[cur] + distu[cur]);
		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;





	
	
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:110:5: warning: unused variable 'ans' [-Wunused-variable]
  110 |  ll ans = 0;
      |     ^~~

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