Submission #1037399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037399		mateuszwes	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	459 ms	93964 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define F first
#define S second
#define pb push_back
#define pi pair<int,int>
#define pl pair<ll,ll>
 
using namespace std;
constexpr int debug = 0;
constexpr int N = 2e6+7;

vector<pl> adj[N];
ll dist[N][4];			//dist from s, t, u, v
ll best[N][2];
bool visited[N][2];
int n, m, s, t, u, v;
ll target;

void addEdge(ll a, ll b, ll val){
	adj[a].pb({b, val});
	adj[b].pb({a, val});
}

void dijkstra(int start, int num){
	priority_queue<pl> Q;
	dist[start][num] = 0;
	Q.push({0, start});

	while(!Q.empty()){
		pl cur = Q.top();
		Q.pop();
		if(dist[cur.S][num] == -1) continue;
		for(auto k: adj[cur.S]){
			if(dist[k.F][num] == -1 || dist[k.F][num] > dist[cur.S][num]+k.S){
				dist[k.F][num] = dist[cur.S][num]+k.S;
				Q.push({-dist[k.F][num], k.F});
			}
		}
	}
}

void dfs(int cur, bool mode){		//cur is the current vertex, mode determines whether dist from s or t should increase
	visited[cur][mode] = 1;
	if(best[cur][mode] == 0) best[cur][mode] = cur;
	for(auto k: adj[cur]){
		if(dist[k.F][0]+dist[k.F][1] == target){
			if(dist[k.F][mode] > dist[cur][mode]){
				if(!visited[k.F][mode]) dfs(k.F, mode);
				if(dist[best[cur][mode]][3] > dist[best[k.F][mode]][3]) best[cur][mode] = best[k.F][mode];
			}
		}
	}
	if(mode && (cur <= n)){
		(dist[best[cur][0]][3] < dist[best[cur][1]][3]) ? adj[cur].pb({best[cur][0]+n, 0}) : adj[cur].pb({best[cur][1]+n, 0});
	}
	if(debug) cout << "EXIT " << cur << ' ' << mode << ' ' << best[cur][mode] << endl;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> s >> t >> u >> v;

	for(int i = 0; i < m; i++){
		ll a1, a2, a3; cin >> a1 >> a2 >> a3;
		addEdge(a1, a2, a3);
		addEdge(a1+n, a2+n, a3);
	}
	for(int i = 0; i <= 2*n+1; i++){
		for(int j = 0; j < 4; j++) dist[i][j] = -1;
		if((i > 0) && (i <= n)) adj[i].pb({i+n, 0});
	}

	dijkstra(v, 3);
	dijkstra(t, 1);
	dijkstra(s, 0);

	target = dist[t][0];		//distance from s to t

	/*
	for(int j = 0; j < 4; j++){
		for(int i = 1; i <= n; i++){
			if(debug) cout << "DISTANCE " << i << ' ' << dist[i][j] << endl;
		}
	}
	*/
	

	dfs(s, 0);
	dfs(t, 1);
	dijkstra(u,2);
	cout << dist[v+n][2];


	return 0;
}

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