Submission #1203775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203775		chawinkn	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	153 ms	17676 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, 9e18), distT(100009, 91e8), distV(100009, 9e18);
priority_queue<pii,vector<pii>,greater<pii>> pq;

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 (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);
	sp(distV, V);
	int ans=9e18;
	for (int i = 1; i <= n; i++)
		if (distS[i]+distT[i] == distS[T]) 
			ans = min(ans, distV[i]);
	cout << ans;
	return 0;
}

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