제출 #55270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55270		shoemakerjo	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	580 ms	147048 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define maxn 100010
#define ll long long
#define pil pair<ll, ll>
#define pli pair<ll, ll>

int N, M;
int s, t, u, v;

const ll inf = 1LL << 61; //feels big enough

ll dists[maxn], distu[maxn], distv[maxn], distt[maxn], dists2[maxn]; 
bool onpath[maxn]; //starts out as false
bool vis[maxn];
ll smallu[maxn], smallv[maxn]; //store the minimum crossing
//run a triple dijkstra

vector<vector<pil>> adj(maxn);

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M >> s >> t >> u >> v;
	int a, b;
	ll c;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		adj[a].push_back(pil(b, c));
		adj[b].push_back(pil(a, c));
	}
	//guaranteed graph is connected
	priority_queue<pli, vector<pli>, greater<pli>> pq;

	fill(dists, dists+maxn, inf);
	fill(distu, distu+maxn, inf);
	fill(distv, distv+maxn, inf);
	fill(distt, distt+maxn, inf);
	dists[s] = 0;
	distu[u] = 0;
	distv[v] = 0;
	distt[t] = 0;
	pq.push(pli(0, s));
	while (pq.size()) {
		pil cur = pq.top(); pq.pop();
		int x = cur.second;
		ll d = cur.first;
		if (d > dists[x]) continue;
		for (pil nx : adj[x]) {
			if (d + nx.second < dists[nx.first]) {
				dists[nx.first] = d + nx.second;
				pq.push(pil(dists[nx.first], nx.first));
			}
		}
	}
	//now we run it for u and then we will do v
	pq.push(pli(0, u));
	while (pq.size()) {
		pil cur = pq.top(); pq.pop();
		int x = cur.second;
		ll d = cur.first;
		if (d > distu[x]) continue;
		for (pil nx : adj[x]) {
			if (d + nx.second < distu[nx.first]) {
				distu[nx.first] = d + nx.second;
				pq.push(pil(distu[nx.first], nx.first));
			}
		}
	}
	pq.push(pli(0, v));
	while (pq.size()) {
		pil cur = pq.top(); pq.pop();
		int x = cur.second;
		ll d = cur.first;
		if (d > distv[x]) continue;
		for (pil nx : adj[x]) {
			if (d + nx.second < distv[nx.first]) {
				distv[nx.first] = d + nx.second;
				pq.push(pil(distv[nx.first], nx.first));
			}
		}
	}

	ll ans = distu[v]; //maybe nothing is on the path
	//now we have to find what is on the path and then we can do the dp thing
	//we can do the dp by just doing another dijkstra from s b/c easy
	//to calculate what is on the path we might want to dijkstra from t??
	onpath[t] = true; // we know that
	//run a modified dijkstra from t, only adding things if they are on the path
	vis[t] = true;
	pq.push(pli(0, t));
	while (pq.size()) {
		pil cur = pq.top(); pq.pop();
		int x= cur.second;
		if (x == s) break; //no need to go further
		ll d = cur.first;
		if (d > distt[x]) continue;
		for (pil nx : adj[x]) {
			if (dists[nx.first] + nx.second != dists[x]) {
				continue; //not on path
			}
			onpath[nx.first] = true;
			if (d + nx.second < distt[nx.first]) {
				distt[nx.first] = d + nx.second;
				pq.push(pil(distt[nx.first], nx.first));
			}
		}
	}
	//now we do the dp stuff
	fill(dists2, dists2+maxn, inf);
	fill(smallu, smallu+maxn, inf);
	fill(smallv, smallv+maxn, inf);
	dists2[s] = 0LL;
	pq.push(pli(0, s));
	while (pq.size()) {
		pil cur = pq.top(); pq.pop();
		int x = cur.second;
		ll d = cur.first;
		if (d > dists2[x]) continue;
	//	cout << "gotten here: " << x << endl;
		smallu[x] = min(smallu[x], distu[x]);
		smallv[x] = min(smallv[x], distv[x]);
		ans = min(ans, smallv[x] + distu[x]);
		ans = min(ans, smallu[x] + distv[x]);
		//process from parents when we go down
		for (pil nx : adj[x]) {
			if (!onpath[nx.first]) continue;
			if (dists[x] + nx.second == dists[nx.first]) {
				smallu[nx.first] = min(smallu[nx.first], smallu[x]);
				smallv[nx.first] = min(smallv[nx.first], smallv[x]);
			}
			if (d + nx.second < dists2[nx.first]) {
				dists2[nx.first] = d + nx.second;
				pq.push(pil(dists2[nx.first], nx.first));
			}
		}

	}
	// for (int i = 1; i <= N; i++) {
	// 	if (onpath[i]) cout << i << " is on the path" << endl;
	// }

	//cout << "printing dist s stuff" << endl;
	// for (int i = 1; i <= N; i++) {
	// 	cout << "     " << dists[i] << endl;
	// }

	//right now i should give <= correct 
	//have to modify the min calculation stuff (should not be hard though)
	// cout << "dist u: " << distu[t] << endl;
	// cout << "dist v: " << distv[t] << endl;
	// cout << "dist s: " << dists[t] << endl;
	// cout << "small u: " << smallu[t] << endl;
	// cout << "small v: " << smallv[t] << endl;
	cout << ans << endl;

}

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