Submission #1027279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027279		nrg_studio	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	186 ms	24388 KiB

commuter_pass

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

#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define mp make_pair
#define f first
#define s second
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	
	int n, m; cin >> n >> m;
	int s, t, u, v; cin >> s >> t >> u >> v;
	int a, b, c;
	vector<vector<pii>> adj(n);

	F0R(i,m) {
		cin >> a >> b >> c;
		adj[--a].pb({--b,c}); adj[b].pb({a,c});
	}
	vector<ll> dist_s(n,LLONG_MAX), dist_u(n,LLONG_MAX),dist_v(n,LLONG_MAX);
	dist_s[--s] = dist_u[--u] = dist_v[--v] = 0; t--;

	auto dijkstra = [&](vector<ll>& ret, int start)->void {
		priority_queue<pii,vector<pii>,greater<pii>> pq;
		pq.push({0,start});
		while (pq.size()) {
			pii cur = pq.top(); pq.pop();
			if (cur.f > ret[cur.s]) {continue;}
			for (pii x : adj[cur.s]) {
				if (cur.f+x.s < ret[x.f]) {
					pq.push({ret[x.f]=cur.f+x.s,x.f});
				}
			}
		}
	};
	dijkstra(dist_s,s); dijkstra(dist_u,u); dijkstra(dist_v,v);
	ll ans = dist_u[v];
	vector<bool> vis(n,false);
	auto dfs = [&](auto&& dfs, int cur)->pii {
		vis[cur] = true;
		pii mn = {dist_u[cur],dist_v[cur]};
		for (pii x : adj[cur]) {
			if (dist_s[x.f] == dist_s[cur]-x.s && !vis[x.f]) {
				pii ret = dfs(dfs,x.f);
				mn.f = min(mn.f,ret.f);
				mn.s = min(mn.s,ret.s);
			}
		}
		ans = min(ans,dist_u[cur]+mn.s);
		ans = min(ans,dist_v[cur]+mn.f);
		//cout << cur+1 << ' ' << mn.f << ' ' << mn.s << '\n';
		return mn;
	};
	dfs(dfs,t); cout << ans << '\n';
}

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