제출 #1318821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318821		nhq0914	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	254 ms	22692 KiB

commuter_pass

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

const int maxn = 1e5 + 7;

int N, M, A, B, C, D;
bool vis[maxn];

vector<pair<int, int>> ed, adj[maxn];
vector<int> dag[maxn];

struct vertex{
	long long dis;
	int state, ver;

	bool operator > (const vertex &other) const {return dis > other.dis;}	
};

void dijkstra1(int s, vector<long long> &dis) {
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;

	q.push({dis[s] = 0, s});
	while(!q.empty()){
		auto [d, v] = q.top(); q.pop();
		
		if(d > dis[v]) continue;

		for(auto &[x, w]: adj[v]){
			if(d + w >= dis[x]) continue;
			q.push({dis[x] = d + w, x});
		}
	}
}

long long dijkstra2(){
	std::array<std::vector<long long>, 3> dis;
	for(int i = 0; i < 3; ++i) dis[i].assign(N + 1, (long long)1e18);

	std::priority_queue<vertex, std::vector<vertex>, std::greater<vertex>> pq;

	pq.push({dis[0][C] = 0, 0, C});
	while(!pq.empty()){
		auto [d, s, v] = pq.top();
		pq.pop();

		if(d > dis[s][v]) continue;

		if(s == 1){
			for(int &x: dag[v]){
				if(d >= dis[1][x]) continue;
				pq.push({dis[1][x] = d, 1, x});
			}
		}
		else{
			for(auto &[x, w]: adj[v]){
				if(d + w >= dis[s][x]) continue;
				pq.push({dis[s][x] = d + w, s, x});
			}
		}
		if(s < 2 && dis[s + 1][v] > d){
			pq.push({dis[s + 1][v] = d, s + 1, v});
		}
	}

	return dis[2][D];
}

int main() {
 	// freopen("data.txt", "r", stdin);
//	freopen("path.inp", "r", stdin);
//	freopen("path.out", "w", stdout);

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> N >> M >> A >> B >> C >> D;
	for(int u, v, w; M--;){
		cin >> u >> v >> w;
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}

	vector <long long> fromA(N + 1, (long long)1e18);
	dijkstra1(A, fromA);

	{
		queue<int> q;
	
		q.push(B);
		vis[B] = true;
		while(!q.empty()) {
			int v = q.front(); q.pop();
		
			for(auto &[x, w]: adj[v]){
				if(fromA[v] - w != fromA[x]) continue;
				ed.emplace_back(x, v);
				if(!vis[x]) vis[x] = true, q.push(x);
			}
		}
	}

	for(auto &[u, v]: ed) dag[u].push_back(v);
	long long ans = dijkstra2();

	for(int i = 1; i <= N; ++i) dag[i].clear();
	for(auto &[u, v]: ed) dag[v].push_back(u);
	ans = min(ans, dijkstra2());

	cout << ans;
	return 0;
}

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