Submission #513830

#	Time	Username	Problem	Language	Result	Execution time	Memory
513830		Tizariox	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	689 ms	42600 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<ll, ll>;

#define FOR(i, a, b) for (ll i = a; i < (b); i++)
#define F0R(i, a) for (ll i = 0; i < (a); i++)
#define F0R1(i, a) for (ll i = 1; i <= (a); i++)
#define FORd(i, a, b) for (ll i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (ll i = (a)-1; i >= 0; i--)
#define F0Rd1(i, a) for (ll i = a; i > 0; i--)
#define SORT(vec) sort(vec.begin(), vec.end())
#define S0RT(arr, n) sort(arr, arr + n)

#define pA first
#define pB second
#define MOD 1000000007
#define nl "\n"
#define pb push_back

ll n, m, s, t, u, v;

class cmp {
  public:
	bool operator()(vector<ll> a, vector<ll> b) { return a[1] > b[1]; }
};

ll dist[100000];
vector<pii> adj[100000];
bool inPass[100000];
unordered_set<ll> prevs[100000];

void dijkstra(ll root) { // traceback
	for (ll i = 0; i < n; i++) {
		dist[i] = 1e18;
	}
	dist[root] = 0;
	priority_queue<vector<ll>, vector<vector<ll>>, cmp> nodes;
	nodes.push({root, 0, -1});
	while (!nodes.empty()) {
		ll node = nodes.top()[0];
		ll minDist = nodes.top()[1];
		ll parent = nodes.top()[2];
		nodes.pop();
		if (node == t) {
			return;
		}
		if (minDist != dist[node]) {
			continue;
		}
		for (pii i : adj[node]) {
			ll neighbor = i.pA;
			ll length = i.pB;
			if (dist[node] + length < dist[neighbor]) {
				dist[neighbor] = dist[node] + length;
				nodes.push({neighbor, dist[neighbor], node});
				prevs[neighbor].insert(node);
			} else if (dist[node] + length == dist[neighbor]) {
				prevs[neighbor].insert(node);
			}
		}
	}
}

bool vis[100000];

void dfs(ll node) {
	inPass[node] = true;
	vis[node] = true;
	for (ll i : prevs[node]) {
		if (!vis[i]) {
			dfs(i);
		}
	}
}

ll distU[100000];

ll dijkstraU(ll root) { // traceback
	for (ll i = 0; i < n; i++) {
		distU[i] = 1e18;
	}
	distU[root] = 0;
	priority_queue<vector<ll>, vector<vector<ll>>, cmp> nodes;
	nodes.push({root, 0, -1});
	ll dist1 = -1;
	while (!nodes.empty()) {
		ll node = nodes.top()[0];
		ll minDist = nodes.top()[1];
		ll parent = nodes.top()[2];
		nodes.pop();
		if (inPass[node] && dist1 == -1) {
			minDist = dist1;
		}
		if (minDist != distU[node]) {
			continue;
		}
		for (pii i : adj[node]) {
			ll neighbor = i.pA;
			ll length = i.pB;
			if (distU[node] + length < distU[neighbor]) {
				distU[neighbor] = distU[node] + length;
				nodes.push({neighbor, distU[neighbor], node});
			}
		}
	}
	return (dist1 == -1) ? 1e18 : dist1;
}

ll distV[100000];

ll dijkstraV(ll root) { // traceback
	for (ll i = 0; i < n; i++) {
		distV[i] = 1e18;
	}
	distV[root] = 0;
	priority_queue<vector<ll>, vector<vector<ll>>, cmp> nodes;
	nodes.push({root, 0, -1});
	ll dist1 = -1;
	while (!nodes.empty()) {
		ll node = nodes.top()[0];
		ll minDist = nodes.top()[1];
		ll parent = nodes.top()[2];
		nodes.pop();
		if (inPass[node] && dist1 == -1) {
			minDist = dist1;
		}
		if (minDist != distV[node]) {
			continue;
		}
		for (pii i : adj[node]) {
			ll neighbor = i.pA;
			ll length = i.pB;
			if (distV[node] + length < distV[neighbor]) {
				distV[neighbor] = distV[node] + length;
				nodes.push({neighbor, distV[neighbor], node});
			}
		}
	}
	return (dist1 == -1) ? 1e18 : dist1;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> s >> t >> u >> v;
	s--;
	t--;
	u--;
	v--; 
	// go through and mark every node in shortest paths from S to T as part of the shortest path, since
	// you'll never use more than 1 distinct shortest path going from U to V, as when you switch from one 
	// shortest path to another you're simply creating a new shortest path
	for (ll i = 0; i < m; i++) {
		ll a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		adj[a].pb(pii(b, c));
		adj[b].pb(pii(a, c));
	}
	dijkstra(s);
	dfs(t);
	cout << min(dijkstraU(u) + dijkstraV(v), distU[v]) << nl;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(ll)':
commuter_pass.cpp:44:6: warning: unused variable 'parent' [-Wunused-variable]
   44 |   ll parent = nodes.top()[2];
      |      ^~~~~~
commuter_pass.cpp: In function 'll dijkstraU(ll)':
commuter_pass.cpp:91:6: warning: unused variable 'parent' [-Wunused-variable]
   91 |   ll parent = nodes.top()[2];
      |      ^~~~~~
commuter_pass.cpp: In function 'll dijkstraV(ll)':
commuter_pass.cpp:124:6: warning: unused variable 'parent' [-Wunused-variable]
  124 |   ll parent = nodes.top()[2];
      |      ^~~~~~

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