제출 #134316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134316		tutis	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	407 ms	23196 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;
	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 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45