Submission #1074161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074161		mmdrzada	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	358 ms	31724 KiB

commuter_pass

#include <bits/stdc++.h>
 
using namespace std;

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

#define sep ' '
#define fastIO 	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
const int N = 1e5+100;
const ll LLINF = 2e18;
int n, m, s, t, x, y;
vector<pii> adj[N], adj2[N];
ll dis[N], dist[N], disy[N], Dis[N];
int par[N];
set<pair<int, int>> frees;

void Dij(int src) {
	set<pair<ll, int>> q;
	fill(Dis, Dis+n, LLINF);
	Dis[src] = 0;
	for(auto [u, w]: adj2[src])
		q.insert({w, u});
	while(q.size()) {
		auto [x, v] = *q.begin();
		q.erase(q.begin());
		if (Dis[v] != LLINF)
			continue;
		Dis[v] = x;
		for(auto [u, w]: adj2[v])
			q.insert({0ll+x+w, u});
	}
}

signed main() {
	fastIO;
	cin >> n >> m;
	cin >> s >> t;
	cin >> x >> y;
	assert(s==x);
	s--, t--, x--, y--;
	for(int i = 0 ; i < m ; i ++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[--v].push_back({--u, w});
		adj[u].push_back({v, w});
	}
	set<pair<ll, pair<int, pii>>> q;
	fill(dis, dis+n, LLINF);
	dis[s] = 0;
	for(auto [u, w]: adj[s])
		q.insert({w, {w, {s, u}}});
	while(q.size()) {
		ll x = q.begin()->first;
		int weight = (q.begin()->second).F;
		auto [p, v] = (q.begin()->second).S;
		q.erase(q.begin());
		if (dis[v] != LLINF) {
			if (dis[v] == x) adj2[v].push_back({p, weight});
			continue;
		}
		dis[v] = x;
		adj2[v].push_back({p, weight});
		for(auto [u, w]: adj[v])
			q.insert({0ll+x+w, {w, {v, u}}});
	}
	Dij(t);
	swap(Dis, dist);
	Dij(y);
	swap(Dis, disy);
	ll ans = 2e18;
	for(int i = 0 ; i < n ; i ++) {
		if (dist[i] != LLINF && disy[i] != LLINF) {
			ans = min(ans, disy[i]);
		}
	}
	cout << ans << endl;
	return 0;
}

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