Submission #851402

#	Time	Username	Problem	Language	Result	Execution time	Memory
851402		jmyszka2007	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	316 ms	70052 KiB

commuter_pass

#include <bits/stdc++.h>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class A, class B>
ostream& operator<<(ostream& o, const pair<A, B>& p) {return o << '(' << p.first << ", " << p.second << ')';}
template<size_t Index = 0, typename... Types>
ostream& printTupleElements(ostream& o, const tuple<Types...>& t) {if constexpr (Index < sizeof...(Types)){if(Index > 0){o << ", ";}o << get<Index>(t);printTupleElements<Index + 1>(o, t);}return o;}
template<typename... Types>
ostream& operator<<(ostream& o, const tuple<Types...>& t){o << "(";printTupleElements(o, t);return o << ")";}
template<class T>
auto operator<<(ostream& o, const T& x) -> decltype(x.end(), o){o << '{';bool first = true;for (const auto& e : x){if (!first){o << ", ";}o << e;first = false;} return o << '}';}
//#define DEBUG
#ifdef DEBUG
#define fastio()
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'
#define check(x) if (!(x)) { cerr << "Check failed: " << #x << " in line " << __LINE__ << endl; exit(1); }
#else
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(...)
#define check(x) 
#endif
typedef long long ll;
#define pi pair<int, int>
#define pl pair<ll, ll>
#define st first
#define nd second
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
constexpr int LIM = 1e5;
constexpr ll INF = 1e18;
struct res{
	pl minsum = make_pair(INF, INF);
	pl minA = make_pair(INF, INF);
	pl minB = make_pair(INF, INF);
};
gp_hash_table<int, ll>dist[LIM + 10];
res ans[LIM + 10];
vector<pi>g[LIM + 10];
void dji(int s, int n) {
	for(int i = 1; i <= n; i++) {
		dist[s][i] = INF;
	}
	dist[s][s] = 0;
	priority_queue<pair<ll, int> >q;
	q.emplace(0, s);
	while(!q.empty()) {
		int v = q.top().nd;
		ll d = -q.top().st;
		q.pop();
		if(dist[s][v] == d) {
			for(auto &[u, val] : g[v]) {
				if(dist[s][u] > dist[s][v] + val) {
					dist[s][u] = dist[s][v] + val;
					q.emplace(-dist[s][u], u);
				}
			}
		}
	}
}
int U, V;
void cntres(int s, int n) {
	for(int i = 1; i <= n; i++) {
		dist[s][i] = INF;
	}
	dist[s][s] = 0;
	pl tmp = make_pair(dist[V][s], dist[U][s]);
	ans[s].minsum = tmp;
	ans[s].minA = tmp;
	ans[s].minB = tmp;
	priority_queue<pair<ll, int> >q;
	q.emplace(0, s);
	while(!q.empty()) {
		int v = q.top().nd;
		ll d = -q.top().st;
		q.pop();
		if(dist[s][v] == d) {
			for(auto &[u, val] : g[v]) {
				if(dist[s][u] > dist[s][v] + val) {
					pl par1 = make_pair(min(ans[v].minsum.st, dist[V][u]), min(ans[v].minsum.nd, dist[U][u]));
					pl par2 = make_pair(min(ans[v].minA.st, dist[V][u]), min(ans[v].minA.nd, dist[U][u]));
					pl par3 = make_pair(min(ans[v].minB.st, dist[V][u]), min(ans[v].minB.nd, dist[U][u]));
					ans[u].minA = par2;
					ans[u].minB = par3;
					ans[u].minsum = make_pair(INF, INF);
					if(ans[u].minsum.st + ans[u].minsum.nd > par1.st + par1.nd) {
						ans[u].minsum = par1;
					}
					if(ans[u].minsum.st + ans[u].minsum.nd > par2.st + par2.nd) {
						ans[u].minsum = par2;
					}
					if(ans[u].minsum.st + ans[u].minsum.nd > par3.st + par3.nd) {
						ans[u].minsum = par3;
					} 
				}
				else if(dist[s][u] == dist[s][v] + val) {
					debug(v, u);
					pl par1 = make_pair(min(ans[v].minsum.st, dist[V][u]), min(ans[v].minsum.nd, dist[U][u]));
					pl par2 = make_pair(min(ans[v].minA.st, dist[V][u]), min(ans[v].minA.nd, dist[U][u]));
					pl par3 = make_pair(min(ans[v].minB.st, dist[V][u]), min(ans[v].minB.nd, dist[U][u]));
					if(ans[u].minsum.st + ans[u].minsum.nd > par1.st + par1.nd) {
						ans[u].minsum = par1;
					}
					if(ans[u].minsum.st + ans[u].minsum.nd > par2.st + par2.nd) {
						ans[u].minsum = par2;
					}
					if(ans[u].minsum.st + ans[u].minsum.nd > par3.st + par3.nd) {
						ans[u].minsum = par3;
					} 
					if(ans[u].minA.st > par2.st) {
						ans[u].minA = par2;
					}
					if(ans[u].minB.nd > par3.nd) {
						ans[u].minB = par3;
					}
				}
				if(dist[s][u] > dist[s][v] + val) {
					dist[s][u] = dist[s][v] + val;
					q.emplace(-dist[s][u], u);
				}
			}
		}
	}
}
void solve() {
	//ifstream cin("nazwa.in");
	//ofstream cout("nazwa.out");
	int n, m;
	cin >> n >> m;
	int s, t;
	cin >> s >> t;
	cin >> V >> U;
	for(int i = 1; i <= m; i++) {
		int a, b, x;
		cin >> a >> b >> x;
		g[a].eb(b, x);
		g[b].eb(a, x);
	}
	dji(U, n);
	dji(V, n);
	for(int i = 1; i <= n; i++) {
		//debug(i, dist[U][i], dist[V][i]);
	}
	cntres(s, n);
	for(int i = 1; i <= n; i++) {
		//debug(i, ans[i].minsum, ans[i].minA, ans[i].minB);
	}
	cout << min(dist[V][U], ans[t].minsum.st + ans[t].minsum.nd) << '\n';
}
int main() {
	fastio();
	int t = 1;
	//cin >> t;
	while(t--) {
		solve();
	}
}

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