Submission #1029443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029443		ArshiaDadras	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	231 ms	76676 KiB

commuter_pass

/* In the name of Allah */
// Welcome to the Soldier Side!
// Where there's no one here, but me...
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int n, m, s1, t1, s2, t2;
vector<pair<int, int>> adj[N];
long long result, d[N], du[N], dv[N], dp[N][2];

void dijkstra1(int root, long long dst[]) {
	priority_queue<pair<long long, int>> q;
	memset(dst, 63, N * sizeof(long long));
	q.push({dst[root] = 0, root});
	while (!q.empty()) {
		int u = q.top().second;
		q.pop();

		for (auto [v, w]: adj[u])
			if (dst[v] > dst[u] + w) {
				dst[v] = dst[u] + w;
				q.push({-dst[v], v});
			}
	}
}

void dijkstra2(int st, int en) {
	priority_queue<pair<long long, int>> q;
	memset(dp, 63, sizeof dp);
	memset(d, 63, sizeof d);
	q.push({d[st] = 0, st});
	dp[st][0] = du[st];
	dp[st][1] = dv[st];
	while (!q.empty()) {
		int u = q.top().second;
		q.pop();

		for (auto [v, w]: adj[u])
			if (d[v] > d[u] + w) {
				d[v] = d[u] + w;
				q.push({-d[v], v});
				dp[v][0] = min(du[v], dp[u][0]);
				dp[v][1] = min(dv[v], dp[u][1]);
			}
			else if (d[v] == d[u] + w && min(du[v], dp[u][0]) + min(dv[v], dp[u][1]) <= dp[v][0] + dp[v][1]) {
				dp[v][0] = min(du[v], dp[u][0]);
				dp[v][1] = min(dv[v], dp[u][1]);
			}
	}

	result = min(result, dp[en][0] + dp[en][1]);
}

void read_input() {
	cin >> n >> m;
	cin >> s1 >> t1;
	cin >> s2 >> t2;
	s1--, t1--, s2--, t2--;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;

		u--, v--;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
}

void solve() {
	dijkstra1(s2, du);
	dijkstra1(t2, dv);
}

void write_output() {
	result = du[t2];
	dijkstra2(s1, t1);
	dijkstra2(t1, s1);
	cout << result << endl;
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve(), write_output();
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra1(int, long long int*)':
commuter_pass.cpp:20:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |   for (auto [v, w]: adj[u])
      |             ^
commuter_pass.cpp: In function 'void dijkstra2(int, int)':
commuter_pass.cpp:39:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |   for (auto [v, w]: adj[u])
      |             ^

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