Submission #1144843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144843		nuutsnoynton	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	347 ms	22292 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair < ll, ll >;
using plll = pair < ll, pll >;
const ll N = 1e5 + 2;

vector < pll > adj[N];
ll Du[N], Dv[N], n, fn, E[2][N], Di[N], D[N], used[N];
void Djikstra(ll x) {
	ll i, cost, X;
	priority_queue < pll, vector < pll>, greater < pll > > pq;
	for (i =0; i <= n; i ++) D[i] = 1e18;
	pq.push(make_pair(0, x));
	D[x] = 0;
	while(!pq.empty()) {
		x = pq.top().second;
		cost = pq.top().first;
		pq.pop();
		if ( D[x] != cost) continue;
		
		for ( pll P: adj[x]) {
			X = P.first;
			if ( D[X] > D[x] + P.second) {
				D[X] = D[x] + P.second;
				pq.push({D[X], X});
			}
		}
	}
	return ;
}
ll ans;
void Djikstra1(ll x, ll y) {
	ll i, cost, type, par, X;
	priority_queue < pll, vector < pll>, greater < pll > > pq;
	
	for (i =0; i <= n; i ++) E[1][i] = E[0][i] = 1e18, used[i] = 0, Di[i] = 1e18;
	pq.push(make_pair(0, x));
	E[0][x] = Du[x];
	E[1][x] = Dv[x];
	Di[x] = 0;
	while(!pq.empty()) {
		x = pq.top().second;
		cost = pq.top().first;
		pq.pop();
		if ( Di[x] != cost) continue;
		for ( pll P : adj[x]) {
			X = P.first;
			if (Di[X] < Di[x] + P.second) continue;
			if ( Di[X] > Di[x] + P.second) {
				E[0][X] = min(E[0][x], Du[X]);
				E[1][X] = min(E[1][x], Dv[X]);
				Di[X] = cost + P.second;
				pq.push(make_pair(cost + P.second, X));
			}
			else {
				if (min(E[0][x], Du[X]) + min(E[1][x], Dv[X]) < E[0][X] + E[1][X]) {
					E[0][X] = min(E[0][x], Du[X]);
					E[1][X] = min(E[1][x], Dv[X]);
				}
			}
		}
	}
	ans = min(ans, E[0][y] + E[1][y]);
	return ;
}
int main() {
	ll m, r, x, y, i,u, v, s, X,  j, t, c,st, st1, fn1;

	cin >> n >> m;
	
	cin >> s >> t;
	cin >> u >> v;
	for (i = 1; i <= m; i ++) {
		cin >> x >> y >> c;
		adj[x].push_back({y, c});
		adj[y].push_back({x, c});
	}
	Djikstra(u);
	for (i = 0; i <= n; i ++) Du[i]= D[i];
	Djikstra(v);
	for (i = 0; i <= n; i ++) Dv[i]= D[i];
	ans= Du[v];
	Djikstra1(s, t);
	Djikstra1(t, s);
	cout << ans << endl;
}

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