Submission #1106758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106758		axiom0510	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	265 ms	38136 KiB

commuter_pass

#include <bits/stdc++.h>

#define FAST() cin.tie(0)->sync_with_stdio(0)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) (int)((x).size())

#define deb(x) cout << #x << " : " << (x) << endl
#define deb_pair(x, y) cout << "(" << #x << ", " << #y << ") : (" << (x) << ", " << (y) << ")" << endl
#define deb_triplet(x, y, z) cout << "(" << #x << ", " << #y << ", " << #z << ") : (" << (x) << ", " << (y) << ", " << (z) << ")" << endl
#define deb_tuple(s) \
	cout << #s << " : " << "["; \
	for (int __i = 0; __i < SIZE(s); __i++) { \
		cout << s[__i]; \
		if (__i != SIZE(s) - 1) cout << ", "; \
	} \
	cout << "]" << endl

using namespace std;

int main() {
	FAST();

	int n, m;
	cin >> n >> m;

	int s, t, u, v;
	cin >> s >> t >> u >> v;

	vector<vector<pair<int, long long>>> adj(n + 1);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;

		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}

	// shortest path s - t
	auto spt = [&](int s, int t) {
		priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
		vector<long long> d(n + 1, 1e18);

		pq.emplace(0, s);
		d[s] = 0;

		while (!pq.empty()) {
			auto [w, x] = pq.top();
			pq.pop();

			if (d[x] != w) continue;

			for (auto [nx, c] : adj[x]) {
				auto nw = w + c;
				if (d[nx] > nw) {
					pq.emplace(nw, nx);
					d[nx] = nw;
				}
			}
		}

		queue<int> q;
		vector<int> b(n + 1);
		vector<vector<pair<int, long long>>> adj_p(n + 1);

		q.push(t);
		b[t] = true;

		while (!q.empty()) {
			auto x = q.front();
			q.pop();

			for (auto [nx, c] : adj[x]) {
				if (d[nx] + c == d[x]) {
					adj_p[nx].emplace_back(x, 0);
					if (!b[nx]) {
						q.push(nx);
						b[nx] = true;
					}
				}
			}
		}

		return adj_p;
		};

	auto gd = spt(s, t), gdt = spt(t, s);

	priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> pq;
	vector<vector<long long>> d(4, vector<long long>(n + 1, 1e18));

	pq.emplace(0, 0, u);
	d[0][u] = 0;

	while (!pq.empty()) {
		auto [w, y, x] = pq.top();
		pq.pop();

		if (d[y][x] != w) continue;

		if (y == 0) {
			if (d[1][x] > w) {
				pq.emplace(w, 1, x);
				d[1][x] = w;
			}
			if (d[2][x] > w) {
				pq.emplace(w, 2, x);
				d[2][x] = w;
			}
		}
		if (y == 1 || y == 2) {
			if (d[3][x] > w) {
				pq.emplace(w, 3, x);
				d[3][x] = w;
			}
		}

		for (auto [nx, c] : (y == 1 ? gd[x] : (y == 2 ? gdt[x] : adj[x]))) {
			auto nw = w + c;
			if (d[y][nx] > nw) {
				pq.emplace(nw, y, nx);
				d[y][nx] = nw;
			}
		}
	}

	long long min = 1e18;
	for (int y = 0; y < 4; y++) {
		min = ::min(min, d[y][v]);
	}

	cout << min << '\n';
}

Compilation message (stderr)

commuter_pass.cpp: In lambda function:
commuter_pass.cpp:47:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |    auto [w, x] = pq.top();
      |         ^
commuter_pass.cpp:52:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |    for (auto [nx, c] : adj[x]) {
      |              ^
commuter_pass.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |    for (auto [nx, c] : adj[x]) {
      |              ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:95:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |   auto [w, y, x] = pq.top();
      |        ^
commuter_pass.cpp:117:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |   for (auto [nx, c] : (y == 1 ? gd[x] : (y == 2 ? gdt[x] : adj[x]))) {
      |             ^

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