제출 #1110993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1110993		haianhnguyen08102007	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	222 ms	24716 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll			long long
#define ld			long double
#define all(x)		x.begin(), x.end()
#define pii			pair<int, int>
#define fi			first
#define se			second
#define pb			emplace_back

template <class T>
inline bool maximize(T &a, const T &b) {return (a < b ? (a = b, 1) : 0);}
template <class T>
inline bool minimize(T &a, const T &b) {return (a > b ? (a = b, 1) : 0);}

const int N = 1e5 + 5;
const ll INF = 1e18;

int n, m, s, t, u, v;
vector<pii> adj[N];
vector<int> par[N], child[N];
ll disU[N], disV[N], disS[N];
bool reach[N];
ll f[N], g[N], ans;

void dijkstra(int st, ll dis[N]){
	fill(dis, dis+n+1, INF);
	dis[st] = 0;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
	q.push({0, st});
	while (q.size()){
		int cur = q.top().se;
		ll curW = q.top().fi;
		q.pop();

		if (dis[cur] != curW) continue;

		for (auto[nxt, w] : adj[cur])
			if (minimize(dis[nxt], curW + w))
				q.push({dis[nxt], nxt});
	}
}

void Dijkstra(int st, ll dis[N]){
	fill(dis, dis+n+1, INF);
	dis[st] = 0;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
	q.push({0, st});
	while (q.size()){
		int cur = q.top().se;
		ll curW = q.top().fi;
		q.pop();

		if (dis[cur] != curW) continue;

		for (auto[nxt, w] : adj[cur]){
			if (minimize(dis[nxt], curW + w)){
				q.push({dis[nxt], nxt});
				par[nxt].clear();
				par[nxt].push_back(cur);
			}else if (dis[nxt] == curW + w){
				par[nxt].push_back(cur);
			}
		}
	}
}

ll dfs(int cur){
	if (f[cur] != -1) return f[cur];
	ll best = disV[cur];
	for (int nxt : par[cur])
		minimize(best, dfs(nxt));
	return f[cur] = best;
}

ll Dfs(int cur){
	if (g[cur] != -1) return g[cur];
	ll best = disV[cur];
	for (int nxt : child[cur])
		minimize(best, Dfs(nxt));
	return g[cur] = best;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m >> s >> t >> u >> v;
	for (int i = 1; i <= m; ++i){
		int a, b, w;
		cin >> a >> b >> w;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}

	dijkstra(u, disU);
	dijkstra(v, disV);
	Dijkstra(s, disS);

	queue<int> q;
	q.push(t);
	while (q.size()){
		int cur = q.front();
		q.pop();
		if (!reach[cur]){
			reach[cur] = 1;
			for (int nxt : par[cur]){
				child[nxt].push_back(cur);
				q.push(nxt);
			}
		}
	}

	memset(f, -1, sizeof f);
	memset(g, -1, sizeof g);
	ans = disU[v];
	for (int i = 1; i <= n; ++i)
		if (reach[i])
			minimize(ans, disU[i] + min(dfs(i), Dfs(i)));
	cout << ans;
}

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