Submission #97824

#	Time	Username	Problem	Language	Result	Execution time	Memory
97824		Anai	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	570 ms	30912 KiB

commuter_pass

#include <bits/stdc++.h>
#define x first
#define y second
#define int i64
using namespace std;

using i64 = long long;
using pii = pair<int, int>;
using pll = pair<i64, i64>;

const int N = 1e5 + 5;

vector<pii> g[N];
vector<int> dag[N];
i64 dist[N], dist_fst[N], dist_snd[N], dp[N][3];
int reach[N], in_deg[N];

vector<int> topsort;
int n, m, src, snk, fst, snd;


static void dijkstra(int nod, i64 dist[N]) {
	priority_queue<pll> pq;

	memset(dist, 0x3f, N * sizeof(i64));
	dist[nod] = 0;
	pq.emplace(dist[nod], nod);

	while (!pq.empty()) {
		i64 dst = -pq.top().x;
		int u = pq.top().y;

		pq.pop();
		if (dst != dist[u])
			continue;

		for (auto v: g[u]) if (dist[v.x] > dst + v.y) {
			dist[v.x] = dst + v.y;
			pq.emplace(-dist[v.x], v.x); } } }

static void make_dag() {
	function<void(int)> dfs1 = [&](int u) {
		reach[u] = 1;
		for (auto v: g[u])
			if (reach[v.x] == 0 && dist[u] - v.y == dist[v.x])
				dfs1(v.x); };
	function<void(int)> dfs2 = [&](int u) {
		reach[u] = 2;
		for (auto v: g[u])
			if (reach[v.x] == 1 && dist[u] + v.y == dist[v.x]) {
				dfs2(v.x);
				dag[u].push_back(v.x); } };

	dfs1(snk);
	dfs2(src); }

static void make_topsort() {
	function<void(int)> dfs = [&](int u) {
		for (auto v: dag[u]) if (--in_deg[v] == 0)
			dfs(v);
		topsort.push_back(u); };

	for (int u = 1; u <= n; ++u)
		for (auto v: dag[u])
			in_deg[v]+= 1;

	topsort.reserve(n);
	dfs(src); }

static void get_dp() {
	for (auto u: topsort) {
		dp[u][0] = dist_fst[u];
		dp[u][1] = dist_snd[u];
		dp[u][2] = dist_fst[u] + dist_snd[u];

		for (auto v: dag[u]) {
			// fst
			dp[u][0] = min(dp[u][0], dp[v][0]);
			// snd
			dp[u][1] = min(dp[u][1], dp[v][1]);
			// both
			dp[u][2] = min(dp[u][2], dp[v][2]);
			dp[u][2] = min(dp[u][2], dp[v][0] + dist_snd[u]);
			dp[u][2] = min(dp[u][2], dp[v][1] + dist_fst[u]); } } }


main() {
#ifdef HOME
	freopen("joi_commuter.in", "r", stdin);
	freopen("joi_commuter.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	cin >> src >> snk;
	cin >> fst >> snd;

	for (int u, v, c, i = 0; i < m; ++i) {
		cin >> u >> v >> c;
		g[u].emplace_back(v, c);
		g[v].emplace_back(u, c); }

	dijkstra(src, dist);
	dijkstra(fst, dist_fst);
	dijkstra(snd, dist_snd);
	make_dag();
	make_topsort();
	get_dp();

	cout << min(dist_fst[snd], dp[src][2]) << '\n';

	return 0; }

Compilation message (stderr)

commuter_pass.cpp:87:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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