Submission #134316

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
134316	2019-07-22T12:11:48 Z	tutis	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	407 ms	23196 KB

commuter_pass

/*input
6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
	ios_base::sync_with_stdio(false);
	ll n, m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	vector<pair<ll, ll>>adj[n + 1];
	vector<ll>adj1[n + 1];
	while (m--)
	{
		ll u, v, c;
		cin >> u >> v >> c;
		adj[u].push_back({v, c});
		adj[v].push_back({u, c});
	}
	ll D[n + 1];
	fill_n(D, n + 1, ll(1e18));
	D[s] = 0;
	priority_queue<pair<ll, ll>>Q;
	Q.push({0, s});
	vector<bool>jau(n + 1, false);
	while (!Q.empty())
	{
		ll a = Q.top().second;
		Q.pop();
		if (jau[a])
			continue;
		jau[a] = true;
		for (pair<ll, ll> b : adj[a])
		{
			if (D[b.first] > D[a] + b.second)
			{
				D[b.first] = D[a] + b.second;
				Q.push({ -D[b.first], b.first});
			}
		}
	}
	vector<bool>buvau(n + 1, false);
	queue<int>QQ;
	QQ.push(t);
	while (!QQ.empty())
	{
		ll a = QQ.front();
		QQ.pop();
		for (pair<ll, ll> b : adj[a])
		{
			if (D[b.first] == D[a] - b.second)
			{
				adj1[b.first].push_back(a);
				adj1[a].push_back(b.first);
				if (buvau[b.first] == false)
				{
					buvau[b.first] = true;
					QQ.push(b.first);
				}
			}
		}
	}
	fill_n(D, n + 1, ll(1e18));
	D[u] = 0;
	vector<bool>jau1(n + 1, false);
	Q.push({ -1, u});
	while (!Q.empty())
	{
		ll a = Q.top().second;
		Q.pop();
		if (jau1[a])
			continue;
		jau1[a] = true;
		for (ll b : adj1[a])
		{
			if (D[b] > D[a])
			{
				D[b] = D[a];
				Q.push({ -D[b], b});
			}
		}
		for (pair<ll, ll> b : adj[a])
		{
			if (D[b.first] > D[a] + b.second)
			{
				D[b.first] = D[a] + b.second;
				Q.push({ -D[b.first], b.first});
			}
		}
	}
	cout << D[v] << "\n";
}

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	283 ms	18408 KB	Output is correct
2	Correct	307 ms	17520 KB	Output is correct
3	Correct	337 ms	18664 KB	Output is correct
4	Correct	271 ms	21304 KB	Output is correct
5	Correct	322 ms	21864 KB	Output is correct
6	Correct	299 ms	22256 KB	Output is correct
7	Correct	355 ms	22128 KB	Output is correct
8	Correct	316 ms	21864 KB	Output is correct
9	Correct	282 ms	21748 KB	Output is correct
10	Correct	261 ms	21996 KB	Output is correct
11	Correct	147 ms	14172 KB	Output is correct
12	Correct	367 ms	21652 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	310 ms	18540 KB	Output is correct
2	Correct	327 ms	21104 KB	Output is correct
3	Correct	349 ms	21936 KB	Output is correct
4	Correct	303 ms	20976 KB	Output is correct
5	Correct	308 ms	22256 KB	Output is correct
6	Correct	327 ms	22376 KB	Output is correct
7	Correct	407 ms	23196 KB	Output is correct
8	Correct	310 ms	20944 KB	Output is correct
9	Correct	319 ms	22276 KB	Output is correct
10	Correct	308 ms	20852 KB	Output is correct
11	Correct	221 ms	14968 KB	Output is correct
12	Correct	328 ms	22256 KB	Output is correct

Subtask #3

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	1784 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Incorrect	2 ms	376 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #4

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	283 ms	18408 KB	Output is correct
2	Correct	307 ms	17520 KB	Output is correct
3	Correct	337 ms	18664 KB	Output is correct
4	Correct	271 ms	21304 KB	Output is correct
5	Correct	322 ms	21864 KB	Output is correct
6	Correct	299 ms	22256 KB	Output is correct
7	Correct	355 ms	22128 KB	Output is correct
8	Correct	316 ms	21864 KB	Output is correct
9	Correct	282 ms	21748 KB	Output is correct
10	Correct	261 ms	21996 KB	Output is correct
11	Correct	147 ms	14172 KB	Output is correct
12	Correct	367 ms	21652 KB	Output is correct
13	Correct	310 ms	18540 KB	Output is correct
14	Correct	327 ms	21104 KB	Output is correct
15	Correct	349 ms	21936 KB	Output is correct
16	Correct	303 ms	20976 KB	Output is correct
17	Correct	308 ms	22256 KB	Output is correct
18	Correct	327 ms	22376 KB	Output is correct
19	Correct	407 ms	23196 KB	Output is correct
20	Correct	310 ms	20944 KB	Output is correct
21	Correct	319 ms	22276 KB	Output is correct
22	Correct	308 ms	20852 KB	Output is correct
23	Correct	221 ms	14968 KB	Output is correct
24	Correct	328 ms	22256 KB	Output is correct
25	Correct	13 ms	1784 KB	Output is correct
26	Correct	2 ms	376 KB	Output is correct
27	Incorrect	2 ms	376 KB	Output isn't correct
28	Halted	0 ms	0 KB	-