Submission #1001541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001541		Tsagana	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	286 ms	21196 KiB

commuter_pass

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define lnl long long
#define pii pair<int, int>
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

const lnl inf = INT_MAX;

int perm[100001];
int n, m, s, t, u, v;
lnl dis1[100001], dis2[100001];
lnl disu[100001], disv[100001];
lnl low1[100001], low2[100001];
bool vis1[100001], vis2[100001];

set<pii> marked;
vector<pii> adj[100001];

lnl dfs1(int i) {
	if (vis1[i]) return low1[i];
	low1[i] = disv[i]; vis1[i] = 1;
	
	for (auto [j, d]: adj[i]) {
		if (dis1[i] + d + dis2[j] == dis1[t])
			low1[i] = min(low1[i], dfs1(j));
	}
	return low1[i];
}
 
lnl dfs2(int i) {
	if (vis2[i]) return low2[i];
	low2[i] = disv[i]; vis2[i] = 1;
	
	for (auto [j, d]: adj[i]) {
		if (dis2[i] + d + dis1[j] == dis1[t])
			low2[i] = min(low2[i], dfs2(j));
	}
	return low2[i];
}

void solve () {
	cin >> n >> m >> s >> t >> u >> v;
 	s--; t--; u--; v--;
 
	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c; a--; b--;
		adj[a].pb({b, c}); adj[b].pb({a, c});
	}
 
	pq<pii, vector<pii>, greater<pii>> q;
	fill(dis1, dis1 + n, inf);
	dis1[s] = 0;
	q.push({0, s});
	while (!q.empty()) {
		auto [d, cur] = q.top(); q.pop();
		if (d > dis1[cur]) continue;
		for (auto [i, d2]: adj[cur]) {
			if (d + d2 < dis1[i]) {
				q.push({d + d2, i});
				dis1[i] = d + d2;
			}
		}
	}
	fill(dis2, dis2 + n, inf);
	dis2[t] = 0;
	q.push({0, t});
	while(!q.empty()){
		auto [d, cur] = q.top();
		q.pop();
		if (d > dis2[cur]) continue;
		for (auto [i, d2]: adj[cur]) {
			if (d + d2 < dis2[i]) {
				q.push({d + d2, i});
				dis2[i] = d + d2;
			}
		}
	}
	
	fill(disu, disu + n, inf);
	disu[u] = 0;
	q.push({0, u});
	while(!q.empty()){
		auto [d, cur] = q.top(); q.pop();
		if (d > disu[cur]) continue;
		for (auto [i, d2]: adj[cur]) {
			if (d + d2 < disu[i]) {
				q.push({d + d2, i});
				disu[i] = d + d2;
			}
		}
	}
	
	fill(disv, disv + n, inf);
	disv[v] = 0;
	q.push({0, v});
	while(!q.empty()){
		auto [d, cur] = q.top(); q.pop();
		if (d > disv[cur]) continue;
		for (auto [i, d2]: adj[cur]) {
			if (d + d2 < disv[i]) {
				q.push({d + d2, i});
				disv[i] = d + d2;
			}
		}
	}
 
	lnl res = inf;
	for (int i = 0; i < n; i++) {
		res = min(res, dfs1(i) + disu[i]);
		res = min(res, dfs2(i) + disu[i]);
	}
	cout << res;
}
int main() {IOS solve(); return 0;}

Compilation message (stderr)

commuter_pass.cpp: In function 'long long int dfs1(int)':
commuter_pass.cpp:34:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |  for (auto [j, d]: adj[i]) {
      |            ^
commuter_pass.cpp: In function 'long long int dfs2(int)':
commuter_pass.cpp:45:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |  for (auto [j, d]: adj[i]) {
      |            ^
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:66:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |   auto [d, cur] = q.top(); q.pop();
      |        ^
commuter_pass.cpp:68:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |   for (auto [i, d2]: adj[cur]) {
      |             ^
commuter_pass.cpp:79:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |   auto [d, cur] = q.top();
      |        ^
commuter_pass.cpp:82:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |   for (auto [i, d2]: adj[cur]) {
      |             ^
commuter_pass.cpp:94:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |   auto [d, cur] = q.top(); q.pop();
      |        ^
commuter_pass.cpp:96:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |   for (auto [i, d2]: adj[cur]) {
      |             ^
commuter_pass.cpp:108:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |   auto [d, cur] = q.top(); q.pop();
      |        ^
commuter_pass.cpp:110:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  110 |   for (auto [i, d2]: adj[cur]) {
      |             ^

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