Submission #235513

#	Time	Username	Problem	Language	Result	Execution time	Memory
235513		ruler	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	861 ms	96708 KiB

commuter_pass

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

#define int ll
#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 5e5 + 5;

int DIS[6][N];
vector<pii> G[3][N];
set<pii> S;

void Dijkstra(int src, int g, int d[]) {
	d[src] = 0, S.insert(make_pair(0, src));
	while (!S.empty()) {
		int v = S.begin()->second; S.erase(S.begin());
		for (auto [u, w] : G[g][v]) if (d[v] + w < d[u]) {
			S.erase(make_pair(d[u], u));
			d[u] = d[v] + w;
			S.insert(make_pair(d[u], u));
		}
	}
}

int32_t main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));

	int n, m; cin >> n >> m;
	int s, t, l, r; cin >> s >> t >> l >> r;
	for (int i = 1; i <= m; i++) {
		int v, u, w; cin >> v >> u >> w;
		G[0][v].push_back(make_pair(u, w));
		G[0][u].push_back(make_pair(v, w));
	}
	memset(DIS, 63, sizeof DIS);
	Dijkstra(s, 0, DIS[0]);
	Dijkstra(t, 0, DIS[1]);
	Dijkstra(l, 0, DIS[2]);
	Dijkstra(r, 0, DIS[3]);
	for (int v = 1; v <= n; v++) {
		for (auto [u,w] : G[0][v]) if (DIS[0][v] + w == DIS[0][u] && DIS[0][v] + w + DIS[1][u] == DIS[0][t]) {
			G[1][v].push_back(make_pair(u, 0));
			G[2][u].push_back(make_pair(v, 0));
		}
		G[1][l].push_back(make_pair(v, DIS[2][v]));
		G[2][l].push_back(make_pair(v, DIS[2][v]));
		G[1][v].push_back(make_pair(r, DIS[3][v]));
		G[2][v].push_back(make_pair(r, DIS[3][v]));
	}
	int ans = INF;
	Dijkstra(l, 1, DIS[4]);
	ans = min(ans, DIS[4][r]);
	Dijkstra(l, 2, DIS[5]);
	ans = min(ans, DIS[5][r]);
	cout << ans << endl;

	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void Dijkstra(ll, ll, ll*)':
commuter_pass.cpp:32:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   for (auto [u, w] : G[g][v]) if (d[v] + w < d[u]) {
             ^
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:58:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   for (auto [u,w] : G[0][v]) if (DIS[0][v] + w == DIS[0][u] && DIS[0][v] + w + DIS[1][u] == DIS[0][t]) {
             ^

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