제출 #1020515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1020515		sinatbtfard	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	722 ms	27712 KiB

commuter_pass

#include <bits/stdc++.h>

#define ll long long
#define pb push_back

using namespace std;

const int maxn = 1e5 + 1;

int n, m, S, T, U, V;
ll dist[2][maxn], dist2[3][maxn];
vector <pair <int, ll>> adj[maxn];
set <pair <ll, int>> s;
set <pair <ll, pair <int, int>>> s2;

void dijkstra (int src, int x){
	fill(dist[x], dist[x] + n + 1, 1e15);
	dist[x][src] = 0;
	s.insert({dist[x][src], src});
	for (int i = 0; i < n; i++){
		int v = (*s.begin()).second;
		s.erase(s.begin());
		for (auto [u, w] : adj[v]){
			if (dist[x][u] <= dist[x][v] + w)
				continue;
			s.erase({dist[x][u], u});
			dist[x][u] = dist[x][v] + w;
			s.insert({dist[x][u], u});
		}
		if (!s.size())
			break;
	}
}

void dijkstra2 (){
	for (int i = 0; i < 3; i++)
		fill(dist2[i], dist2[i] + n + 1, 1e15);
	dist2[0][U] = 0;
	s2.insert({dist2[0][U], {U, 0}});
	for (int i = 0; i < 3 * n; i++){
		int v = (*s2.begin()).second.first, st = (*s2.begin()).second.second;
		s2.erase(s2.begin());
		for (auto [u, w] : adj[v]){
			if (dist[0][v] + dist[1][u] + w == dist[0][T] && st != 2){
				if (dist2[1][u] <= dist2[st][v] + w)
					continue;
				s2.erase({dist2[1][u], {u, 1}});
				dist2[1][u] = dist2[st][v];
				s2.insert({dist2[1][u], {u, 1}});
				continue;
			}
			if (st == 1){
				if (dist2[2][u] <= dist2[st][v] + w)
					continue;
				s2.erase({dist2[2][u], {u, 2}});
				dist2[2][u] = dist2[st][v] + w;
				s2.insert({dist2[2][u], {u, 2}});
				continue;
			}
			if (dist2[st][u] <= dist2[st][v] + w)
				continue;
			s2.erase({dist2[st][u], {u, st}});
			dist2[st][u] = dist2[st][v] + w;
			s2.insert({dist2[st][u], {u, st}});
		}
		if (!s2.size())
			break;
	}
}

void dijkstra3 (){
	for (int i = 0; i < 3; i++)
		fill(dist2[i], dist2[i] + n + 1, 1e15);
	dist2[0][U] = 0;
	s2.insert({dist2[0][U], {U, 0}});
	for (int i = 0; i < 3 * n; i++){
		int v = (*s2.begin()).second.first, st = (*s2.begin()).second.second;
		s2.erase(s2.begin());
		for (auto [u, w] : adj[v]){
			if (dist[0][u] + dist[1][v] + w == dist[0][T] && st != 2){
				if (dist2[1][u] <= dist2[st][v] + w)
					continue;
				s2.erase({dist2[1][u], {u, 1}});
				dist2[1][u] = dist2[st][v];
				s2.insert({dist2[1][u], {u, 1}});
				continue;
			}
			if (st == 1){
				if (dist2[2][u] <= dist2[st][v] + w)
					continue;
				s2.erase({dist2[2][u], {u, 2}});
				dist2[2][u] = dist2[st][v] + w;
				s2.insert({dist2[2][u], {u, 2}});
				continue;
			}
			if (dist2[st][u] <= dist2[st][v] + w)
				continue;
			s2.erase({dist2[st][u], {u, st}});
			dist2[st][u] = dist2[st][v] + w;
			s2.insert({dist2[st][u], {u, st}});
		}
		if (!s2.size())
			break;
	}
}

int main (){
	ios_base::sync_with_stdio(0);
	cin >> n >> m >> S >> T >> U >> V;
	for (int x, y, z, i = 0; i < m; i++){
		cin >> x >> y >> z;
		adj[x].pb({y, z});
		adj[y].pb({x, z});
	}
	dijkstra(S, 0);
	dijkstra(T, 1);
	dijkstra2();
	ll ans = min(dist2[0][V], min(dist2[1][V], dist2[2][V]));
	dijkstra3();
	cout << min(ans, min(dist2[0][V], min(dist2[1][V], dist2[2][V])));
}

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