Submission #145417

#	Time	Username	Problem	Language	Result	Execution time	Memory
145417		peijar	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	928 ms	25908 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Arete
{
	ll v, c;
};

struct Situation
{
	ll u, dis;

	bool operator<(Situation other) const
	{
		return (dis > other.dis or (dis == other.dis and u > other.u));
	}
};

const int MAXN = 1e5;
const ll INF = 1e18;
const int U = 0;
const int V = 1;
const int S = 2;
const int T = 3;

vector<Arete> G[MAXN];
ll dis[4][MAXN];
ll uv_from_st[4][4][MAXN];
ll u_from_s[MAXN], v_from_s[MAXN], u_from_t[MAXN];
int special_nodes[4];
int nb_noeuds, nb_aretes;
int u, v, s, t;

void read_input(void)
{
	cin >> nb_noeuds >> nb_aretes;
	cin >> s >> t;
	cin >> u >> v;
	s--, t--, u--, v--;
	special_nodes[U] = u, special_nodes[V] = v, special_nodes[S]=s, special_nodes[T]=t;

	for (int i(0); i < nb_aretes; ++i)
	{
		int a, b;
		ll c;
		cin >> a >> b >> c;
		G[a-1].push_back({b-1, c});
		G[b-1].push_back({a-1, c});
	}
}

void run_dis(int from)
{
	for (int i(0); i < nb_noeuds; ++i)
		dis[from][i] = INF;

	dis[from][special_nodes[from]] = 0;
	priority_queue<Situation> Q;
	Q.push({special_nodes[from], 0});

	while (!Q.empty())
	{
		auto node = Q.top();
		Q.pop();
		int x = node.u;
		ll d = node.dis;
		if (d > dis[from][x])
			continue;
		for (auto e : G[x])
			if (d + e.c < dis[from][e.v])
			{
				dis[from][e.v] = d+e.c;
				Q.push({e.v, d+e.c});
			}
	}
}

void run_weird_dis(int from, int to)
{
	for (int i(0); i < nb_noeuds; ++i)
		uv_from_st[from][to][i] = INF;

	uv_from_st[from][to][special_nodes[from]] = dis[from][special_nodes[to]];
	priority_queue<Situation> Q;
	Q.push({special_nodes[from], uv_from_st[from][to][special_nodes[from]]});

	while (!Q.empty())
	{
		auto node = Q.top();
		Q.pop();
		int x = node.u;
		ll d = node.dis;
		if (uv_from_st[from][to][x] < d)
			continue ;
		for (auto e : G[x])
			if (dis[from][e.v] == dis[from][x] + e.c && uv_from_st[from][to][e.v] > uv_from_st[from][to][x])
			{
				uv_from_st[from][to][e.v] = min(uv_from_st[from][to][x], dis[to][e.v]);
				Q.push({e.v, uv_from_st[from][to][e.v]});
			}
	}
}

int		main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	read_input();
	for (int i(0); i < 4; ++i)
		run_dis(i);
	for (int from(2); from < 4; ++from)
		for (int to(0); to < 2; ++to)
			run_weird_dis(from, to);

	ll shortest = dis[U][v];

	for (int x(0); x < nb_noeuds; ++x)
	{
		if (dis[S][x] + dis[T][x] == dis[S][t])
		{
			shortest = min(shortest, min(uv_from_st[S][U][x] + dis[V][x], uv_from_st[T][V][x] + dis[U][x]));
			shortest = min(shortest, min(uv_from_st[S][V][x] + dis[U][x], uv_from_st[T][U][x] + dis[V][x]));
		}
	}

	cout << shortest << endl;
}

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