Submission #248380

#	Time	Username	Problem	Language	Result	Execution time	Memory
248380		Berted	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	540 ms	40428 KiB

commuter_pass

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
#define ll long long
#define pii pair<ll, ll>
#define fst first
#define snd second
#define vi vector<ll>
#define vpi vector<pii>

using namespace std;

const ll MX = 1e18;

int n, m, s, t, u, v;
vpi adj[100001] = {};
vpi keepTrack[100001] = {};
vi par[100001] = {};
ll dst[2][100001], ret = MX, dst2[100001] = {};
bitset<100001> bt;

/* Idea : Run SSSP for both U and V, then start Dijkstra from S to T
		  Each traversal, we keep all possible pairs of (dist_U, dist_V)
		  When traversing to a new node, notice that we only need to push
		  (min dist_U, dist_V) and (dist_U, min dist_V)

		  After it is finished, backtrack all possible paths, as there exists some
		  cases that might not be counted
		  i.e. (2, 9), (3, 3), (9, 2) -> (3, 3) is not pushed, therefore it might be
		  possible that all future paths are unable to minimize (2, 9) or (9, 2)
		  Therefore the optimal would still have been (3, 3).
*/

inline void solveSSSP(int s, bool b)
{
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	for (int i = 0; i < n; i++) dst[b][i] = -1;
	pq.push({0, s});
	while (pq.size())
	{
		int u = pq.top().snd; ll c = pq.top().fst; pq.pop();
		if (dst[b][u] == -1)
		{
			// cout << "DIJKSTRA - " << b << " " << u << " " << c << "\n";
			dst[b][u] = c;
			for (pii v : adj[u]) pq.push({c + v.snd, v.fst});
		}
	}
}

inline void specialTrav(int s, int t)
{
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	dst2[s] = 0;
	pq.push({0, s});
	while (pq.size())
	{
		int u = pq.top().snd; ll c = pq.top().fst; pq.pop();
		if (dst2[u] == c)
		{
			pii tp1 = {dst[0][u], dst[1][u]}, tp2 = tp1;
			keepTrack[u].push_back(tp1);
			for (pii &pos : keepTrack[u])
			{
				pos.fst = min(pos.fst, dst[0][u]); pos.snd = min(pos.snd, dst[1][u]);
				if (pos < tp1) tp1 = pos;
				if (make_pair(pos.snd, pos.fst) < make_pair(tp2.snd, tp2.fst)) tp2 = pos;
			}
			if (u == t) break;
			for (pii v : adj[u])
			{
				if (c + v.snd < dst2[v.fst]) 
				{
					par[v.fst].clear(); 
					keepTrack[v.fst].clear(); 
					dst2[v.fst] = c + v.snd; 
					pq.push({c + v.snd, v.fst});
				}
				if (c + v.snd == dst2[v.fst]) 
				{
					keepTrack[v.fst].push_back(tp1); 
					keepTrack[v.fst].push_back(tp2); 
					par[v.fst].push_back(u);
				}
			}
		}
	}
}

inline void bktrk(int t)
{
	for (int i = 0; i < n; i++) dst2[i] = -1;
	queue<int> q;
	q.push(t);
	while (q.size())
	{
		int u = q.front(); q.pop();
		for (auto v : keepTrack[u]) {ret = min(ret, v.fst + v.snd);}
		for (auto v : par[u])
		{
			if (!bt[v]) {bt[v] = 1; q.push(v);}
		}
	}
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	cin >> s >> t >> u >> v; s--; t--; u--; v--;
	for (int i = 0; i < n; i++)
	{
		dst[0][i] = dst[1][i] = -1;
		dst2[i] = MX;
	}
	for (int i = 0; i < m; i++)
	{
		int a, b, c; cin >> a >> b >> c;
		adj[a - 1].push_back({b - 1, c});
		adj[b - 1].push_back({a - 1, c});
	}
	solveSSSP(u, 0);
	solveSSSP(v, 1);
	specialTrav(s, t);
	bktrk(t);
	/*
	for (int i = 0; i < n; i++)
	{
		cout << "Node " << i << ": \n";
		for (auto pos : keepTrack[i])
		{
			cout << pos.fst << ", " << pos.snd << "\n";
		}
	}
	*/

	cout << min(dst[0][v], ret) << "\n";
	return 0;
}

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