Submission #41153

#	Time	Username	Problem	Language	Result	Execution time	Memory
41153		aome	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	539 ms	19928 KiB

commuter_pass

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

const int N = 100005;
const long long INF = 1e18;

int n, m;
int S, T, U, V;
long long dis[N][2];
long long f[N][4];
vector< pair<int, int> > G[N];

struct Data {
	long long value;
	int node, type;

	Data() {}

	Data (long long value, int node, int type) : 
		value(value), node(node), type(type) {}

	void debug() {
		cout << "# " << value << ' ' << node << ' ' << type << '\n';
	}

	bool operator < (const Data& rhs) const {
		return value > rhs.value;
	}
};

void dijkstra(int start, bool type) {
	for (int i = 1; i <= n; ++i) dis[i][type] = INF;
	priority_queue<Data> pq;
	dis[start][type] = 0, pq.push(Data(0, start, type));
	while (pq.size()) {
		Data u = pq.top(); pq.pop();
		if (u.value != dis[u.node][u.type]) continue;
		for (auto i : G[u.node]) {
			Data v = u; v.value += i.second, v.node = i.first;
			if (v.value < dis[v.node][v.type]) {
				dis[v.node][v.type] = v.value, pq.push(v);
			} 
		}
	}
}

void solve() {
	for (int i = 1; i <= n; ++i) {
		f[i][0] = f[i][1] = f[i][2] = f[i][3] = INF;
	}
	priority_queue<Data> pq;
	f[U][0] = 0, pq.push(Data(0, U, 0));
	while (pq.size()) {
		Data u = pq.top(), v; pq.pop();
		if (u.value != f[u.node][u.type]) continue;
		// u.debug();
		if (u.type == 0) {
			if (dis[u.node][0] + dis[u.node][1] == dis[T][0]) {
				v = u; 
				v.type = 1;
				if (f[v.node][1] > v.value) {
					f[v.node][1] = v.value, pq.push(v);
				}
				v.type = 2;
				if (f[v.node][2] > v.value) {
					f[v.node][2] = v.value, pq.push(v);
				}
			}
		}
		if (u.type == 1 || u.type == 2) {
			v = u, v.type = 3;
			if (f[v.node][3] > v.value) {
				f[v.node][3] = v.value, pq.push(v);
			}
			if (u.type == 1) {
				for (auto i : G[u.node]) {
					v = u, v.node = i.first;
					if (dis[u.node][0] + i.second + dis[v.node][1] == dis[T][0] && f[v.node][1] > v.value) {
						f[v.node][1] = v.value, pq.push(v);
					}   
				}
			}
			else {
				for (auto i : G[u.node]) {
					v = u, v.node = i.first;
					if (dis[u.node][1] + i.second + dis[v.node][0] == dis[T][0] && f[v.node][2] > v.value) {
						f[v.node][2] = v.value, pq.push(v);
					}   
				}
			}
		}
		if (u.type == 0 || u.type == 3) {
			for (auto i : G[u.node]) {
				v = u, v.value += i.second, v.node = i.first;
				if (f[v.node][v.type] > v.value) {
					f[v.node][v.type] = v.value, pq.push(v);
				}
			}
		}
	}
	cout << min(f[V][3], f[V][0]);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	cin >> S >> T >> U >> V;
	for (int i = 0; i < m; ++i) {
		int u, v, c; cin >> u >> v >> c;
		G[u].push_back(make_pair(v, c));
		G[v].push_back(make_pair(u, c));
	}
	dijkstra(S, 0), dijkstra(T, 1), solve();
}

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