Submission #963802

#	Time	Username	Problem	Language	Result	Execution time	Memory
963802		raspy	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	536 ms	35388 KiB

commuter_pass

#include <bits/stdc++.h>

#define inf 1'000'000'000'000'000
#define int long long

using namespace std;
typedef pair<int, int> ii;

vector<ii> graf[100005];
int du[100005];
int dv[100005];
int ds[100005];
int dp[5][100005];
int rez = 0;
bool ob[100005];

void dijkstra1(int start, int arr[])
{
	memset(ob, false, sizeof(ob));

	priority_queue<ii, vector<ii>, greater<ii>> pq;
	pq.push({0, start});
	while (!pq.empty())
	{
		auto [d, u] = pq.top();
		pq.pop();
		if (ob[u])
			continue;
		arr[u] = d;
		ob[u] = 1;
		for (auto [v, w] : graf[u])
			pq.push({d + w, v});
	}
}

void dijkstra2(int start, int end)
{
	memset(dp, -1, sizeof(dp));
	memset(ob, false, sizeof(ob));
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
	pq.push({0, start, 0});
	dp[0][0] = dp[1][0] = inf;
	while (!pq.empty())
	{
		auto [d, u, par] = pq.top();
		pq.pop();
		if (!ob[u])
		{
			ob[u] = 1;
			ds[u] = d;
			dp[0][u] = min(du[u], dp[0][par]);
			dp[1][u] = min(dv[u], dp[1][par]);
			for (auto [v, w] : graf[u])
				pq.push({d + w, v, u});
		}
		else if (d == ds[u])
		{
			if (min(du[u], dp[0][par]) + min(dv[u], dp[1][par]) <= dp[0][u] + dp[1][u])
			{
				dp[0][u] = min(du[u], dp[0][par]);
				dp[1][u] = min(dv[u], dp[1][par]);
			}
		}
	}
	rez = min(rez, dp[0][end] + dp[1][end]);
}

int32_t main()
{
	int n, m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		graf[a].push_back({b, c});
		graf[b].push_back({a, c});
	}
	dijkstra1(u, du);
	dijkstra1(v, dv);
	rez = du[v];
	dijkstra2(s, t);
	dijkstra2(t, s);
	cout << rez << '\n';
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra1(long long int, long long int*)':
commuter_pass.cpp:25:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |   auto [d, u] = pq.top();
      |        ^
commuter_pass.cpp:31:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |   for (auto [v, w] : graf[u])
      |             ^
commuter_pass.cpp: In function 'void dijkstra2(long long int, long long int)':
commuter_pass.cpp:45:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |   auto [d, u, par] = pq.top();
      |        ^
commuter_pass.cpp:53:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |    for (auto [v, w] : graf[u])
      |              ^

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