Submission #755199

#	Time	Username	Problem	Language	Result	Execution time	Memory
755199		siewjh	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	384 ms	36428 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
const ll inf = 1e18;
int nodes, edges;
vector<pair<int, ll>> adj[MAXN];
void dijkstra(int source, vector<ll> &dist){
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	pq.push({0, source});
	for (int i = 1; i <= nodes; i++) dist[i] = inf;
	dist[source] = 0;
	while (!pq.empty()){
		ll d = pq.top().first; int x = pq.top().second; pq.pop();
		if (dist[x] != d) continue;
		for (auto nxt : adj[x]){
			int nn = nxt.first; ll nd = nxt.second;
			if (d + nd < dist[nn]){
				dist[nn] = d + nd;
				pq.push({dist[nn], nn});
			}
		}
	}
}
ll dp(int x, vector<vector<int>> &spadj, vector<ll> &ddest, vector<ll> &memo){
	if (memo[x] != -1) return memo[x];
	ll ans = ddest[x];
	for (int nxt : spadj[x]) ans = min(ans, dp(nxt, spadj, ddest, memo));
	return memo[x] = ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int s, t, u, v; cin >> nodes >> edges >> s >> t >> u >> v;
	vector<tuple<int, int, ll>> elist(edges);
	for (int i = 0; i < edges; i++){
		int a, b; ll d; cin >> a >> b >> d;
		adj[a].push_back({b, d});
		adj[b].push_back({a, d});
		elist[i] = {a, b, d};
	}
	vector<ll> ds(nodes + 1), dt(nodes + 1), du(nodes + 1), dv(nodes + 1);
	dijkstra(s, ds); dijkstra(t, dt); dijkstra(u, du); dijkstra(v, dv);
	ll dst = ds[t];
	vector<vector<int>> stot(nodes + 1), ttos(nodes + 1);
	for (auto edge : elist){
		int a, b; ll d; tie(a, b, d) = edge;
		if (ds[a] + d + dt[b] == dst){
			stot[a].push_back(b);
			ttos[b].push_back(a);
		}
		else if (ds[b] + d + dt[a] == dst){
			stot[b].push_back(a);
			ttos[a].push_back(b);
		}
	}
	vector<ll> memo1(nodes + 1, -1), memo2(nodes + 1, -1);
	ll ans = du[v];
	for (int i = 1; i <= nodes; i++) ans = min(ans, du[i] + dp(i, stot, dv, memo1));
	for (int i = 1; i <= nodes; i++) ans = min(ans, du[i] + dp(i, ttos, dv, memo2));
	cout << ans;
}

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