Submission #963797

#	Time	Username	Problem	Language	Result	Execution time	Memory
963797		raspy	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	2069 ms	29528 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <cstring>

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

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

vector<pair<int, int>> graf[100005];
vector<int> par[100005];
pair<int, int> dp[100005];

void dij(int st, vector<int>& dist, bool dg = false)
{
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	pq.push({0, st});
	dist[st] = 0;
	while (!pq.empty())
	{
		auto [d, u] = pq.top();
		pq.pop();
		if (d > dist[u])
			continue;
		for (auto [v, w] : graf[u])
		{
			if (dist[v] != -1 && d+w > dist[v])
				continue;
			if (dg)
			{
				if (d+w == dist[v])
				{
					par[v].push_back(u);
					continue;
				}
				par[v].clear();
				par[v].push_back(u);
				// cout << u << "->" << v << "\n";
			}
			else if (d+w == dist[v])
				continue;
			dist[v] = d+w;
			pq.push({dist[v], v});
		}
	}
}

int gl = 0;
pair<int, int> dfs(vector<int>& dist1, vector<int>& dist2, int vz)
{
	if (dp[vz].first != 0)
		return dp[vz];
	pair<int, int> rez = {dist1[vz], dist2[vz]};
	for (int v : par[vz])
	{
		gl++;
		auto[nu, nv] = dfs(dist1, dist2, v);
		gl--;
		if (nu < rez.first)
		{
			rez.first = nu;
			rez.second = min(dist2[vz], nv);
		}
		else if (nv < rez.second)
		{
			rez.second = nv;
			rez.first = min(dist1[vz], nu);
		}
	}
	return dp[vz] = rez;
}

int32_t main()
{
	int n, m;
	cin >> n >> m;
	int s, t;
	cin >> s >> t;
	int u, v;
	cin >> u >> v;
	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		graf[u].push_back({v, w});
		graf[v].push_back({u, w});
	}
	vector<int> dist2(n+1, -1);
	vector<int> dist3(n+1, -1);
	dij(s, dist2, true);
	fill(dist2.begin(), dist2.end(), -1);
	dij(u, dist2);
	dij(v, dist3);
	int rez = dist2[v];
	pair<int, int> par = dfs(dist2, dist3, t);
	cout << min(rez, par.first+par.second) << "\n";
	// for (int i = 1; i <= n; i++)
	// 	cout << dp[i].first << " " << dp[i].second << "\n";
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dij(long long int, std::vector<long long int>&, bool)':
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:29:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |   for (auto [v, w] : graf[u])
      |             ^
commuter_pass.cpp: In function 'std::pair<long long int, long long int> dfs(std::vector<long long int>&, std::vector<long long int>&, long long int)':
commuter_pass.cpp:61:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |   auto[nu, nv] = dfs(dist1, dist2, v);
      |       ^

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