Submission #891924

#	Time	Username	Problem	Language	Result	Execution time	Memory
891924		goodspeed0208	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	383 ms	22612 KiB

commuter_pass

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<utility>
#define int long long
#define INF 1000000000000000000
#define pii pair<long long, long long>
using namespace std;

struct DS{
	int a, b, c;
};

signed main() {
	int n, m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	vector<vector<pii> >G(n+1);
	int a, b, c;
	while (m--) {
		cin >> a >> b >> c;
		G[a].push_back({b, c});
		G[b].push_back({a, c});
	}
	vector<int>sdis(n+5, INF), tdis(n+5, INF), vdis(n+5, INF);
	sdis[s] = 0;
	set<pii>q; q.insert({0, s});
	while (!q.empty()) {
		auto tmp = *q.begin(); q.erase(q.begin());
		int len = tmp.first, i = tmp.second;
		//cout << i << " " << len << "\n";
		if (len > sdis[i]) continue;
		
		for (auto &j : G[i]) {
			if (sdis[j.first] < len + j.second) continue;
			if (sdis[j.first] != INF) {
				q.erase({sdis[j.first], j.first});
			}
			sdis[j.first] = len + j.second;
			q.insert({sdis[j.first], j.first});
		}
	}
	tdis[t] = 0;
	q.insert({0, t});
	while (!q.empty()) {
		auto tmp = *q.begin(); q.erase(q.begin());
		int len = tmp.first, i = tmp.second;
		//cout << i << " " << len << "\n";
		if (len > tdis[i]) continue;
		
		for (auto &j : G[i]) {
			if (tdis[j.first] < len + j.second) continue;
			if (tdis[j.first] != INF) {
				q.erase({tdis[j.first], j.first});
			}
			tdis[j.first] = len + j.second;
			q.insert({tdis[j.first], j.first});
		}
	}
	vdis[v] = 0;
	q.insert({0, v});
	while (!q.empty()) {
		auto tmp = *q.begin(); q.erase(q.begin());
		int len = tmp.first, i = tmp.second;
		//cout << i << " " << len << "\n";
		if (len > vdis[i]) continue;
		
		for (auto &j : G[i]) {
			if (vdis[j.first] < len + j.second) continue;
			if (vdis[j.first] != INF) {
				q.erase({vdis[j.first], j.first});
			}
			vdis[j.first] = len + j.second;
			q.insert({vdis[j.first], j.first});
		}
	}
	int minroute = INF;
	for (int i = 1 ; i <= n ; i++) {
		minroute = min(minroute, sdis[i] + tdis[i]);
	}
	int ans = INF;
	for (int i = 1 ; i <= n ; i++) {
		if (sdis[i] + tdis[i] == minroute) {
			ans = min(ans, vdis[i]);
		}
	}
	cout << ans << "\n";
}

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