Submission #988308

#	Time	Username	Problem	Language	Result	Execution time	Memory
988308		BF001	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	333 ms	38288 KiB

commuter_pass

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

#define N 100005
#define int long long
#define oo 1e18
#define fi first
#define se second

typedef pair<int, int> ii;

/*
	1 --> s
	2 --> t
	3 --> u
	4 --> v
*/

int n, m, d[5][N], s, t, u, v, dp1[3][N], dp2[3][N], in1[N], in2[N];
vector<ii> adj[N];
vector<int> ddj[N], djj2[N];

void ditra(int typ, int s){
	for (int i = 1; i <= n; i++){
		d[typ][i] = oo;
	}
	d[typ][s] = 0;
	priority_queue<ii, vector<ii>, greater<ii>> q;
	q.push({0, s});
	while (!q.empty()){
		int u = q.top().se;
		int du = q.top().fi;
		q.pop();
		if (du != d[typ][u]) continue;
		for (auto x : adj[u]){
			int v = x.fi;
			int dv = x.se;
			if (d[typ][v] > du + dv){
				d[typ][v] = du + dv;
				q.push({d[typ][v], v});
			}
		}
	}
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> m;
 	cin >> s >> t;
 	cin >> u >> v;
    for (int i = 1; i <= m; i++){
    	int u, v, w;
    	cin >> u >> v >> w;
    	adj[u].push_back({v, w});
    	adj[v].push_back({u, w});
    }

    ditra(1, s);
    ditra(2, t);
    ditra(3, u);
    ditra(4, v);

    for (int i = 1; i <= n; i++){
    	dp1[1][i] = dp2[1][i] = d[3][i];
    	dp1[2][i] = dp2[2][i] = d[4][i];
    }

	queue<int> q;
	q.push(s);	
	
	for (int i = 1; i <= n; i++){
		for (auto x : adj[i]){
			int v = x.fi;
			int w = x.se;
			if (d[1][i] + w + d[2][v] == d[2][s]){
				ddj[i].push_back(v);
				in1[v]++;
				in2[i]++;
				djj2[v].push_back(i);
			}
		}
	}

	while (!q.empty()){
		int u = q.front();
		q.pop();
		for (auto x : ddj[u]){
			in1[x]--;
			dp1[1][x] = min(dp1[1][x], dp1[1][u]);
			dp1[2][x] = min(dp1[2][x], dp1[2][u]);
			if (!in1[x]) q.push(x);
		}
	}

	int res = d[3][v];
	q.push(t);
	while (!q.empty()){
		int u = q.front();
		q.pop();
		res = min(res, dp2[1][u] + dp1[2][u]);
		res = min(res, dp2[2][u] + dp1[1][u]);
		for (auto x : djj2[u]){
			in2[x]--;
			dp2[1][x] = min(dp2[1][x], dp2[1][u]);
			dp2[2][x] = min(dp2[2][x], dp2[2][u]);
			if (!in2[x]) q.push(x);
		}
	}

	cout << res;

    return 0;
}     

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