Submission #851256

#	Time	Username	Problem	Language	Result	Execution time	Memory
851256		Hakiers	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	335 ms	23852 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];
long long pass[MAXN][2];
long long passprice;
int n;

void preprocces(int a, int x){
	
	for(int i = 1; i <= n; i++) pass[i][x] = oo;
	
	priority_queue<pair<long long, int>> Q;
	Q.push({0, a});
	
	while(Q.size()){
		auto [d, v] = Q.top();
		Q.pop();
		
		if(pass[v][x] <= -d) continue;
		pass[v][x] = -d;
		
		
		for(auto [u, c] : G[v]){
			if(pass[u][x] <= pass[v][x] + c) continue;
	
			
			Q.push({-(pass[v][x] + c), u});
		}
	}
	
	
	
}


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){
			if(cost[v][1] > -d) Q.push({d, v, 1});
			if(cost[v][2] > -d) Q.push({d, v, 2});
		}
		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(cost[u][s] <= cost[v][s]) continue;
				if(pass[v][0] + c + pass[u][1] != passprice) continue;
				//cout << pass[v][0] << " " << pass[u][1] << endl;
				//cout << "s: " << s << " u: " << u << " v: " << v << " cost: " << cost[v][s] << endl;
				
				if(pass[u][0] > pass[v][0])
					Q.push({-cost[v][s], u, s});
			}
			else if(s == 2){
				if(cost[u][s] <= cost[v][s]) continue;
				if(pass[u][0] + c + pass[v][1] != passprice) continue;
				//cout << "s: " << s << " u: " << u << " v: " << v << " cost: " << cost[v][s] << endl;
				
				if(pass[u][1] > pass[v][1])
					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, 0);
	preprocces(t, 1);
	passprice = pass[t][0];
	
	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";
	//cout << cost[1][3] << endl;


}

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