제출 #891927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
891927		goodspeed0208	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	424 ms	26896 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);
	vector<DS>routes;
	int a, b, c;
	while (m--) {
		cin >> a >> b >> c;
		G[a].push_back({b, c});
		G[b].push_back({a, c});
		routes.push_back({a, b, 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});
		}
	}
	int minroute = INF;
	vector<int>onroute(n+1, 0);
	for (int i = 1 ; i <= n ; i++) {
		minroute = min(minroute, sdis[i] + tdis[i]);
	}
	for (int i = 1 ; i <= n ; i++) {
		if (sdis[i] + tdis[i] == minroute) {
			onroute[i] = 1;
		}
	}
	if (s == u) {
		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 ans = INF;
		for (int i = 1 ; i <= n ; i++) {
			if (sdis[i] + tdis[i] == minroute) {
				ans = min(ans, vdis[i]);
			}
		}
		cout << ans << "\n";
	} else {
		for (auto &i : routes) {
			if (onroute[i.a] && onroute[i.b]) {
				i.c = 0;
			}
		}
		for (int i = 1 ; i <= n ; i++) G[i].clear();
		for (auto &i : routes) {
			G[i.a].push_back({i.b, i.c});
			G[i.b].push_back({i.a, i.c});
		}
		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});
			}
		}
		cout << vdis[u] << "\n";
	}
		
}

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