Submission #1203794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203794		chawinkn	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	148 ms	18620 KiB

commuter_pass

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

#define int long long
#define pii pair<int,int>

vector<pii> g[100009];
vector<int> distS(100009, 1e18), distT(100009, 1e18), distU(100009, 1e18), distV(100009, 1e18);
priority_queue<pii,vector<pii>,greater<pii>> pq;
bool cp[100009];

void sp(vector<int>& dist, int u) {
	pq.push({dist[u]=0, u});
	while (!pq.empty()) {
		auto [d,u]=pq.top(); pq.pop();
		for (auto [v,w] : g[u]) {
			if (cp[u] && cp[v])
				w = 0;
			if (d+w < dist[v])
				pq.push({dist[v]=d+w, v});
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, m, S, T, U, V;
	cin >> n >> m >> S >> T >> U >> V;
	while (m--) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	sp(distS, S), sp(distT, T);
	for (int i = 1; i <= n; i++)
		cp[i] = distS[i]+distT[i] == distS[T];
	sp(distU, U);
	cout << distU[V];
	return 0;
}

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