Submission #1049059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049059		pacman	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	490 ms	48840 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long int

using namespace std;

const int maxn = 1e5 + 100, inf = 1e15 + 10;

int n ,m, S, T ,U ,V;

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

int dp[4][maxn] ,dist[2][maxn];
set<pair<int ,int>> s;
set<vector<int>> s2;


void djkasra(int num){
	for(int i = 0 ;i < n; i++){
		int v = (*s.begin()).second;
		s.erase(s.begin());
		for(auto [u ,w] : adj[v]){
			if(dist[num][u] > dist[num][v] + w){
				s.erase({dist[num][u], u});
				dist[num][u] = dist[num][v] + w;
				s.insert({dist[num][u], u});
			}
		}
		if(s.size() == 0) break;
	}
}


void daiikasra(){
	while(s2.size() > 0){
		vector<int> p = (*s2.begin());
		int v = p[1];
		int state = p[2];
		s2.erase(s2.begin());
		//s2 has first ==> distance / second.first ==> vertice / second.second ==> state
		if(state == 0){
			//here we are updating out dp of state 0
			//dist[0][T] == minimum path between S and T
			for(auto [u , w] : adj[v]){
				//here we are checking edges that only belong to the shortest path DAG
				if(dist[0][v] + dist[1][u] + w == dist[0][T]){
					if(dp[1][u] > dp[state][v]){
						dp[1][u] = dp[state][v];
						s2.insert({dp[1][u], u, 1});
					}
				}
				if(dist[1][v] + dist[0][u] + w == dist[0][T]){
					if(dp[2][u] > dp[state][v]){
						dp[2][u] = dp[state][v];
						s2.insert({dp[2][u], u, 2});
					}
				}
			}
			for(auto [u , w] : adj[v]){
				//we are updating a state the we dont use the DAG paths
				if(dp[0][u] > dp[state][v] + w){
					dp[0][u] = dp[state][v] + w;
					s2.insert({dp[0][u], u ,0});
				}
			}
		}
		if(state == 1){
			//state we are going the same direction as s to t in DAG
			for(auto [u , w] : adj[v]){
				//here we are checking edges that only belong to the shortest path DAG
				if(dist[0][v] + dist[1][u] + w == dist[0][T]){
					if(dp[1][u] > dp[state][v]){
						dp[1][u] = dp[state][v];
						s2.insert({dp[1][u], u, 1});
					}
				}
				else{
					if(dp[3][u] > dp[state][v] + w){
						dp[3][u] = dp[state][v] + w;
						s2.insert({dp[3][u], u, 3});
					}
				}
			}
		}
		if(state == 2){
			//state we are going the oppisite direction as s to t in DAG (t ==> s)
			for(auto [u , w] : adj[v]){
				//here we are checking edges that only belong to the shortest path DAG
				if(dist[0][u] + dist[1][v] + w == dist[0][T]){
					if(dp[2][u] > dp[state][v]){
						dp[2][u] = dp[state][v];
						s2.insert({dp[2][u], u, 2});
					}
				}
				else{
					if(dp[3][u] > dp[state][v] + w){
						dp[3][u] = dp[state][v] + w;
						s2.insert({dp[3][u], u, 3});
					}
				}
			}
		}
		if(state == 3){
			//state == 3 / state where we finish using the DAG of shortest path from s ==> t and we begin to go to V
			for(auto [u , w] : adj[v]){
				//here we are checking edges that only belong to the shortest path DAG
				if(dp[3][u] > dp[state][v] + w){
					dp[3][u] = dp[state][v] + w;
					s2.insert({dp[3][u], u, 3});
				}
			}
		}
	}
}


int32_t main(){
	
	ios::sync_with_stdio(0) , cout.tie(0) ,cin.tie(0);
	
	cin >> n >> m >> S >> T >> U >> V;
	
	for(int i = 0 ;i < m; i++){
		int x ,y ,z;
		cin >> x >> y >> z;
		
		adj[x].push_back({y , z});
		adj[y].push_back({x , z});
	}
	
	
	for(int i = 0;  i <= n; i++){
		dist[0][i] = inf;
	}
	dist[0][S] = 0;
	for(int i = 1 ;i <= n; i++){
		s.insert({dist[0][i], i});
	}
	djkasra(0);
	
	
	for(int i = 0;  i <= n; i++){
		dist[1][i] = inf;
	}
	dist[1][T] = 0;
	for(int i = 1 ;i <= n; i++){
		s.insert({dist[1][i], i});
	}
	djkasra(1);
	
	
	for(int j = 0 ;j < 4 ; j++){
		for(int i = 0 ;i <= n; i++){
			dp[j][i] = inf;
		}	
	}
	dp[0][U] = 0;
	for(int i = 1 ; i <= n; i++){
		s2.insert({dp[0][i],i ,0});
	}
	daiikasra();
	
	
	cout << min({dp[0][V], dp[1][V] ,dp[2][V], dp[3][V]}) << endl;
	
	return 0;
}

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