oj.uz

Submission #145417

# Submission time Handle Problem Language Result Execution time Memory
145417 2019-08-19T19:54:40 Z peijar Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 928 ms 25908 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 23676 KB Output is correct
2 Correct 635 ms 23140 KB Output is correct
3 Correct 508 ms 23324 KB Output is correct
4 Correct 593 ms 25348 KB Output is correct
5 Correct 578 ms 22828 KB Output is correct
6 Correct 633 ms 23328 KB Output is correct
7 Correct 598 ms 23004 KB Output is correct
8 Correct 529 ms 22904 KB Output is correct
9 Correct 516 ms 23852 KB Output is correct
10 Correct 510 ms 24084 KB Output is correct
11 Correct 260 ms 16220 KB Output is correct
12 Correct 541 ms 23780 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 23860 KB Output is correct
2 Correct 526 ms 23644 KB Output is correct
3 Correct 534 ms 23684 KB Output is correct
4 Correct 551 ms 23472 KB Output is correct
5 Correct 549 ms 23716 KB Output is correct
6 Correct 501 ms 23112 KB Output is correct
7 Correct 557 ms 22996 KB Output is correct
8 Correct 576 ms 23732 KB Output is correct
9 Correct 535 ms 23368 KB Output is correct
10 Correct 547 ms 23264 KB Output is correct
11 Correct 191 ms 16284 KB Output is correct
12 Correct 460 ms 23224 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4472 KB Output is correct
2 Correct 7 ms 2808 KB Output is correct
3 Correct 5 ms 2776 KB Output is correct
4 Correct 27 ms 6184 KB Output is correct
5 Correct 15 ms 4472 KB Output is correct
6 Correct 6 ms 2808 KB Output is correct
7 Correct 7 ms 2940 KB Output is correct
8 Correct 7 ms 3064 KB Output is correct
9 Correct 6 ms 2808 KB Output is correct
10 Correct 16 ms 4472 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 5 ms 2808 KB Output is correct
13 Correct 6 ms 2808 KB Output is correct
14 Correct 5 ms 2808 KB Output is correct
15 Correct 6 ms 2808 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 23676 KB Output is correct
2 Correct 635 ms 23140 KB Output is correct
3 Correct 508 ms 23324 KB Output is correct
4 Correct 593 ms 25348 KB Output is correct
5 Correct 578 ms 22828 KB Output is correct
6 Correct 633 ms 23328 KB Output is correct
7 Correct 598 ms 23004 KB Output is correct
8 Correct 529 ms 22904 KB Output is correct
9 Correct 516 ms 23852 KB Output is correct
10 Correct 510 ms 24084 KB Output is correct
11 Correct 260 ms 16220 KB Output is correct
12 Correct 541 ms 23780 KB Output is correct
13 Correct 514 ms 23860 KB Output is correct
14 Correct 526 ms 23644 KB Output is correct
15 Correct 534 ms 23684 KB Output is correct
16 Correct 551 ms 23472 KB Output is correct
17 Correct 549 ms 23716 KB Output is correct
18 Correct 501 ms 23112 KB Output is correct
19 Correct 557 ms 22996 KB Output is correct
20 Correct 576 ms 23732 KB Output is correct
21 Correct 535 ms 23368 KB Output is correct
22 Correct 547 ms 23264 KB Output is correct
23 Correct 191 ms 16284 KB Output is correct
24 Correct 460 ms 23224 KB Output is correct
25 Correct 16 ms 4472 KB Output is correct
26 Correct 7 ms 2808 KB Output is correct
27 Correct 5 ms 2776 KB Output is correct
28 Correct 27 ms 6184 KB Output is correct
29 Correct 15 ms 4472 KB Output is correct
30 Correct 6 ms 2808 KB Output is correct
31 Correct 7 ms 2940 KB Output is correct
32 Correct 7 ms 3064 KB Output is correct
33 Correct 6 ms 2808 KB Output is correct
34 Correct 16 ms 4472 KB Output is correct
35 Correct 5 ms 2808 KB Output is correct
36 Correct 5 ms 2808 KB Output is correct
37 Correct 6 ms 2808 KB Output is correct
38 Correct 5 ms 2808 KB Output is correct
39 Correct 6 ms 2808 KB Output is correct
40 Correct 500 ms 25816 KB Output is correct
41 Correct 542 ms 23692 KB Output is correct
42 Correct 535 ms 23900 KB Output is correct
43 Correct 213 ms 16376 KB Output is correct
44 Correct 298 ms 16376 KB Output is correct
45 Correct 569 ms 23028 KB Output is correct
46 Correct 585 ms 22732 KB Output is correct
47 Correct 526 ms 23324 KB Output is correct
48 Correct 189 ms 15736 KB Output is correct
49 Correct 440 ms 25908 KB Output is correct
50 Correct 928 ms 22956 KB Output is correct
51 Correct 458 ms 22948 KB Output is correct