Submission #1039576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039576		sssamui	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	284 ms	38424 KiB

commuter_pass

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
using ll = long long;

vector<vector<int>> lstadj(1e5 + 1, vector<int>(0));
vector<int> topsort(0);
vector<bool> vis(1e5 + 1, false);

void dfs(int node)
{
	vis[node] = true;
	for (int nxt : lstadj[node]) if (!vis[nxt]) dfs(nxt);
	topsort.push_back(node);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	vector<vector<pair<ll, int>>> adj(n + 1, vector<pair<ll, int>>(0));
	while (m--)
	{
		int a, b;
		ll c;
		cin >> a >> b >> c;
		adj[a].push_back({ c, b }), adj[b].push_back({ c, a });
	}

	priority_queue<pair<ll, int>> udjk;
	vector<ll> du(n + 1, -1);
	udjk.push({ 0, u });
	while (!udjk.empty())
	{
		ll d = -udjk.top().first;
		int node = udjk.top().second;
		udjk.pop();
		if (du[node] == -1)
		{
			du[node] = d;
			for (pair<ll, int> nxt : adj[node]) udjk.push({ -d - nxt.first, nxt.second });
		}
	}

	vector<ll> dv(n + 1, -1);
	priority_queue<pair<ll, int>> vdjk;
	vdjk.push({ 0, v });
	while (!vdjk.empty())
	{
		ll d = -vdjk.top().first;
		int node = vdjk.top().second;
		vdjk.pop();
		if (dv[node] == -1)
		{
			dv[node] = d;
			for (pair<ll, int> nxt : adj[node]) vdjk.push({ -d - nxt.first, nxt.second });
		}
	}

	vector<ll> ds(n + 1, -1);
	priority_queue<pair<ll, pair<int, int>>> sdjk;
	sdjk.push({ 0, {s, 0} });
	while (!sdjk.empty())
	{
		ll d = -sdjk.top().first;
		int node = sdjk.top().second.first, lst = sdjk.top().second.second;
		sdjk.pop();
		if (d == ds[node]) lstadj[node].push_back(lst);
		else if (ds[node] == -1)
		{
			ds[node] = d;
			if (lst > 0) lstadj[node].push_back(lst);
			for (pair<ll, int> nxt : adj[node]) sdjk.push({ -d - nxt.first, {nxt.second, node} });
		}
	}

	dfs(t);
	vector<int> dtopsort = topsort;
	vector<ll> ddu = du, ddv = dv;
	while (!topsort.empty())
	{
		int node = topsort.back();
		for (int nxt : lstadj[node]) if (vis[nxt]) if (dv[node] < dv[nxt]) dv[nxt] = dv[node];
		topsort.pop_back();
	}

	ll ans = du[n] + dv[n];
	for (int i = 1; i < n; i++) if (du[i] + dv[i] < ans) ans = du[i] + dv[i];
	while (!dtopsort.empty())
	{
		int node = dtopsort.back();
		for (int nxt : lstadj[node]) if (vis[nxt]) if (ddu[node] < ddu[nxt]) ddu[nxt] = ddu[node];
		dtopsort.pop_back();
	}

	for (int i = 1; i < n; i++) if (ddu[i] + ddv[i] < ans) ans = ddu[i] + ddv[i];
	cout << ans;
}

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