제출 #234966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234966		Atalasion	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	872 ms	59680 KiB

commuter_pass

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-O2")
#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000010;
const ll LOG = 25;

int n, m, S, T, V, U;
ll dis[4][N];
vector<pii> G[N];
vector<pii> g[N];

void DJ(int v, int f){
	for (int i = 0; i < N; i++) dis[f][i] = INF;
	set<pii> st;
	st.insert({0, v});
	dis[f][v] = 0;
	while (st.size()){
		pii fr = *st.begin();
		
		st.erase(st.begin());
		for (auto u:G[fr.S]){
			if (dis[f][u.F] > fr.F + u.S){
				st.erase({dis[f][u.F], u.F});
				dis[f][u.F] = fr.F + u.S;
				st.insert({dis[f][u.F], u.F});
			}
		}
	}
}

void DJ2(int v){
	for (int i = 0; i < N; i++) dis[0][i] = INF;
	dis[0][v] = 0;
	set<pii> st;
	st.insert({0, v});
	int f = 0;
	dis[f][v] = 0;
	while (st.size()){
		pii fr = *st.begin();
		st.erase(st.begin());
		for (auto u:g[fr.S]){
			if (dis[f][u.F] > fr.F + u.S){
				st.erase({dis[f][u.F], u.F});
				dis[f][u.F] = fr.F + u.S;
				st.insert({dis[f][u.F], u.F});
			}
		}
	}
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> S >> T >> U >> V;
	for (int i = 1; i <= m; i++){
		ll v, u, w;
		cin >> v >> u >> w;
		G[v].pb({u, w});
		G[u].pb({v, w});
	}
	DJ(S, 0);
	DJ(T, 1);
	DJ(U, 2);
	DJ(V, 3);
	for (int i = 1; i <= n; i++){
//		cout << i << ' ' << dis[0][i] << ' ' << dis[1][i] << endl;
		for (auto u:G[i]){
			if(dis[0][i] + u.S == dis[0][u.F] && dis[1][u.F] + dis[0][u.F] == dis[0][T]){
//				cout <<"YES " << i << ' ' << u.F << endl;
				g[i].pb({u.F, 0}), g[u.F + n].pb({i + n, 0});
			}
		}
		g[U].pb({i, dis[2][i]});
		g[U].pb({i + n, dis[2][i]});
		g[i].pb({V, dis[3][i]});
		g[i + n].pb({V, dis[3][i]});
	}	
	DJ2(U);
	cout << dis[0][V];








	return 0;
}

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