Submission #134308

#	Time	Username	Problem	Language	Result	Execution time	Memory
134308		tutis	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2057 ms	22244 KiB

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;
	queue<ll>Q;
	Q.push(s);
	while (!Q.empty())
	{
		ll a = Q.front();
		Q.pop();
		for (pair<ll, ll> b : adj[a])
		{
			if (D[b.first] > D[a] + b.second)
			{
				D[b.first] = D[a] + b.second;
				Q.push(b.first);
			}
		}
	}
	vector<bool>buvau(n + 1, false);
	Q.push(t);
	while (!Q.empty())
	{
		ll a = Q.front();
		Q.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;
					Q.push(b.first);
				}
			}
		}
	}
	fill_n(D, n + 1, ll(1e18));
	D[u] = 0;
	Q.push(u);
	while (!Q.empty())
	{
		ll a = Q.front();
		Q.pop();
		for (ll b : adj1[a])
		{
			if (D[b] > D[a])
			{
				D[b] = D[a];
				Q.push(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(b.first);
			}
		}
	}
	cout << D[v] << "\n";
}

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