Submission #851210

#	Time	Username	Problem	Language	Result	Execution time	Memory
851210		Hakiers	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2101 ms	23568 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
const long long oo = 1e18;
const int MAXN = 1e5 + 7;
vector<pair<int, int>> G[MAXN];
long long cost[MAXN][4];
int layer[MAXN];
bool visited[MAXN];
int n;

void preprocces(int a, int b){
	
	vector<long long> costd(n+1, oo);
	vector<int> D[MAXN];
	
	priority_queue<tuple<long long, int, int>> Q;
	Q.push({0, a, 0});
	
	while(Q.size()){
		auto [d, v, p] = Q.top();
		Q.pop();
		
		if(costd[v] < -d) continue;
		else if(costd[v] == -d){ 
			if(p != 0) D[v].push_back(p);
			continue;
		}
		
		D[v].clear();
		D[v].shrink_to_fit();
		costd[v] = -d;
		if(p != 0) D[v].push_back(p);
		
		for(auto [u, c] : G[v]){
			if(costd[u] < costd[v] + c) continue;
			else if(costd[u] == costd[v] + c){
				D[u].push_back(v);
				continue;
			}
			
			Q.push({-(costd[v] + c), u, v});
		}
	}
	
	
	
	queue<int> W;
	W.push(b);
	layer[b] = 1;
	
	while(W.size()){
		
		int xd = W.front(); W.pop();
		visited[xd] = 1;
		
		for(auto x : D[xd]){
			if(visited[x]) continue;
			layer[x] = layer[xd] + 1;
			W.push(x);
			visited[x] = 1;
		}
	}
	
	/*
	for(int i = 1; i <= n; i++)
		if(layer[i]) cout << "v: " << i << " layer: " << layer[i] << endl;
	*/
}


void dijkstra(int a){
	// stan 0 jeszcze nie weszlismy na sciezke pass'a
	// stan 1 weszlismy na sciezke pass'a ale idziemy w gore
	// stan 2 weszlismy na sciezka pass'a ale idziemy w dol
	// stan 3 wyszlismy z sciezki pass'a
	priority_queue<tuple<long long, int, int>> Q;
	Q.push({0, a, 0});
	
	while(Q.size()){
		auto [d, v, s] = Q.top(); Q.pop();
		
		if(cost[v][s] <= -d) continue;
		
		cost[v][s] = -d;
		if(s == 0 && layer[v]){
			if(cost[v][1] > -d) Q.push({-d, v, 1});
			if(cost[v][2] > -d) Q.push({-d, v, 2});
		}
		else if(s == 1 || s == 2){
			if(cost[v][3] > -d) Q.push({-d, v, 3});
		}
		
		
		for(auto [u, c] : G[v]){
			if(s == 0 || s == 3){
				if(cost[u][s] <= cost[v][s] + c) continue;
				Q.push({-(cost[v][s] + c), u, s});
			}
			else if(s == 1){
				if(layer[u] <= layer[v] || !layer[u]) continue;
				if(cost[u][s] <= cost[v][s]) continue;
				Q.push({-cost[v][s], u, s});
			}
			else if(s == 2){
				if(layer[u] >= layer[v] || !layer[u]) continue;
				if(cost[u][s] <= cost[v][s]) continue;
				Q.push({-cost[v][s], u, s});
			}
		}
	
	}

}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	
	for(int i = 1; i <= m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		G[a].push_back({b, c});
		G[b].push_back({a, c});
	}
	
	preprocces(s, t);
	
	for(int i = 1; i <= n; i++)
		cost[i][0] = cost[i][1] = cost[i][2] = cost[i][3] = oo;
		
	dijkstra(u);
	
	cout << min({cost[v][0], cost[v][1], cost[v][2], cost[v][3]}) << "\n";


}

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