Submission #87836

#	Time	Username	Problem	Language	Result	Execution time	Memory
87836		KCSC	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	906 ms	152468 KiB

commuter_pass

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

const int DIM = 100005;

long long dst1[DIM], dst2[DIM];

vector<pair<int, int>> edg[DIM];
pair<long long, long long> dp[DIM][4];

void dijkstra(int s, int n, long long dst[DIM]) {
	static priority_queue<pair<long long, int>,
						  vector<pair<long long, int>>,
						  greater<pair<long long, int>>> prq;
	for (int i = 1; i <= n; ++i) {
		dst[i] = (1LL << 50); }
	dst[s] = 0; prq.push(make_pair(0, s));
	while (prq.size()) {
		long long d = prq.top().first; 
		int x = prq.top().second; prq.pop();
		if (dst[x] != d) {
			continue; }
		for (auto &ed : edg[x]) {
			int y = ed.first, c = ed.second;
			if (dst[y] > dst[x] + c) {
				dst[y] = dst[x] + c;	
				prq.push(make_pair(dst[y], y)); } } } }

int main(void) {
#ifdef HOME
	freopen("commuter.in", "r", stdin);
	freopen("commuter.out", "w", stdout);
#endif
	int n, m, s, t, u, v; 
	cin >> n >> m >> s >> t >> u >> v;
	for (int i = 1; i <= m; ++i) {	
		int x, y, c; cin >> x >> y >> c;
		edg[x].push_back(make_pair(y, c)); 
		edg[y].push_back(make_pair(x, c)); }
	dijkstra(u, n, dst1); dijkstra(v, n, dst2);
	priority_queue<pair<pair<long long, long long>, pair<int, int>>, 
				   vector<pair<pair<long long, long long>, pair<int, int>>>,
				   greater<pair<pair<long long, long long>, pair<int, int>>>> prq;	
	for (int i = 1; i <= n; ++i) {
		for (int k = 0; k <= 3; ++k) {
			dp[i][k] = make_pair(1LL << 50, 1LL << 50); } }
	dp[s][0] = make_pair(0LL, 0LL); prq.push(make_pair(make_pair(0LL, 0LL), make_pair(s, 0)));	
	while (prq.size()) {
		pair<long long, long long> d = prq.top().first;
		int x = prq.top().second.first, k = prq.top().second.second; prq.pop();
		if (dp[x][k] != d) {
			continue; }
		if (!(k & 1) and dp[x][k ^ 1] > make_pair(dp[x][k].first, dp[x][k].second + dst1[x])) {
			dp[x][k ^ 1] = make_pair(dp[x][k].first, dp[x][k].second + dst1[x]);
			prq.push(make_pair(dp[x][k ^ 1], make_pair(x, k ^ 1))); }
		if (!(k & 2) and dp[x][k ^ 2] > make_pair(dp[x][k].first, dp[x][k].second + dst2[x])) {
			dp[x][k ^ 2] = make_pair(dp[x][k].first, dp[x][k].second + dst2[x]);
			prq.push(make_pair(dp[x][k ^ 2], make_pair(x, k ^ 2))); }
		for (auto &ed : edg[x]) {
			int y = ed.first, c = ed.second;
			if (dp[y][k] > make_pair(dp[x][k].first + c, dp[x][k].second)) {
				dp[y][k] = make_pair(dp[x][k].first + c, dp[x][k].second);
				prq.push(make_pair(dp[y][k], make_pair(y, k))); } } }
	cout << min(dp[t][3].second, dst1[v]);
	return 0; }

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