Submission #1260328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260328		4QT0R	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	325 ms	31556 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>

vector<pll> graph[100003];
vector<ll> dag[2][100003];
ll deg[2][100003];
ll n, m, S, T, U, V, oo = 1e18 + 1, min_dist;
ll dist[4][100003];
ll wyn[2][100003];

void Dijkstra(ll st, ll par)
{
	fill(dist[par], dist[par] + n + 1, oo);
	dist[par][st] = 0;
	priority_queue<pll, vector<pll>, greater<pll>> pq;
	pq.push({0, st});
	while (pq.size())
	{
		auto [d, v] = pq.top();
		pq.pop();
		if (d != dist[par][v])
			continue;
		for (auto [u, w] : graph[v])
		{
			if (d + w < dist[par][u])
			{
				dist[par][u] = d + w;
				pq.push({d + w, u});
			}
		}
	}
}

void init()
{
	cin >> n >> m >> S >> T >> U >> V;
	ll a, b, c;
	for (ll i = 1; i <= m; i++)
	{
		cin >> a >> b >> c;
		graph[a].push_back({b, c});
		graph[b].push_back({a, c});
	}
	Dijkstra(U, 0);
	Dijkstra(V, 1);
	Dijkstra(S, 2);
	Dijkstra(T, 3);
	min_dist = dist[2][T];
}

void construct()
{
	for (ll v = 1; v <= n; v++)
	{
		for (auto [u, w] : graph[v])
		{
			if ((dist[2][v] + w + dist[3][u]) == min_dist)
			{
				dag[0][v].push_back(u);
				deg[0][u]++;
				dag[1][u].push_back(v);
				deg[1][v]++;
			}
		}
	}
}

void topo_sort(ll typ){
	stack<ll> kol;
	queue<ll> q;
	for (ll i = 1; i <= n; i++)
	{
		if (!deg[typ][i])
			q.push(i);
	}
	while(q.size())
	{
		ll v = q.front();
		q.pop();
		kol.push(v);
		for (ll u : dag[typ][v])
		{
			deg[typ][u]--;
			if (!deg[typ][u])
				q.push(u);
		}
	}
	while(kol.size())
	{
		ll v = kol.top();
		kol.pop();
		wyn[typ][v] = dist[0][v];
		for (auto u : dag[typ][v])
			wyn[typ][v] = min(wyn[typ][v], wyn[typ][u]);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	init();
	ll ans = dist[0][V];
	construct();
	topo_sort(0);
	topo_sort(1);
	for (ll i = 1; i <= n; i++)
	{
		if (dist[2][i] + dist[3][i] == min_dist)
			ans = min(ans, min(wyn[0][i], wyn[1][i]) + dist[1][i]);
	}
	cout << ans << '\n';
}

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