Submission #963678

#	Time	Username	Problem	Language	Result	Execution time	Memory
963678		raspy	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	713 ms	262144 KiB

commuter_pass

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

#define int long long

using namespace std;

vector<tuple<int, int, int>> graf[100005];
unordered_set<int> vs[200005];
int raz[100005];
int raz1[100005];
vector<pair<int, int>> pr[100005];
int oz = 1;
int start = 0;

void oznaci(int u)
{
	if (u == start)
		return;
	bool prv = 1;
	for (auto [v, i] : pr[u])
	{
		if (!prv)
			oz++;
		vs[i].insert(oz);
		oznaci(v);
		prv = 0;
	}
}

int32_t main()
{
	int n, m;
	cin >> n >> m;
	int s, t;
	cin >> s >> t;
	start = s;
	int zc, kn;
	cin >> zc >> kn;
	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		graf[u].push_back({v, w, i});
		graf[v].push_back({u, w, i});
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	raz[s] = -1;
	pq.push({0, s});
	while (!pq.empty())
	{
		auto [d, u] = pq.top();
		pq.pop();
		if (d > raz[u] && raz[u] != -1)
			continue;
		for (auto [v, w, i] : graf[u])
		{
			if (raz[v] && raz[v] < d+w)
				continue;
			if (d+w < raz[v])
				pr[v].clear();
			pr[v].push_back({u, i});
			raz[v] = d+w;
			pq.push({raz[v], v});
		}
	}
	oznaci(t);
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq1;
	for (int to = 1; to <= oz; to++)
		pq1.push({0, zc, to});
	memset(raz1, -1, sizeof(raz1));
	raz1[zc] = 0;
	while (!pq1.empty())
	{
		auto [d, u, zs] = pq1.top();
		// cout<< u << " " << d << "\n";
		pq1.pop();
		if (d > raz1[u] && raz1[u])
			continue;
		if (u == kn)
		{
			cout << d << "\n";
			exit(0);
		}
		for (auto [v, w, i] : graf[u])
		{
			int ns = d;
			// if (v == 4 && u == 2)
			// 	cout << d << " " << zs << " " << w << " " << (vs[i].find(zs) == vs[i].end()) << "\n";
			if (vs[i].empty() || vs[i].find(zs) == vs[i].end())
				ns+=w;
			if ((raz1[v] != -1 && raz1[v] < ns) || (raz1[v] == d))
				continue;
			// if (u == 3 && v == 2)
				// cout << raz1[v] << " " << ns << " " << d << "\n";
			// cout << "-> " << v << "\n";
			raz1[v] = ns;
			pq1.push({raz1[v], v, zs});
		}
	}
	cout << "error\n";
	exit(0);
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void oznaci(long long int)':
commuter_pass.cpp:25:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |  for (auto [v, i] : pr[u])
      |            ^
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:56:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |   auto [d, u] = pq.top();
      |        ^
commuter_pass.cpp:60:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |   for (auto [v, w, i] : graf[u])
      |             ^
commuter_pass.cpp:79:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |   auto [d, u, zs] = pq1.top();
      |        ^
commuter_pass.cpp:89:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |   for (auto [v, w, i] : graf[u])
      |             ^

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