Submission #307529

#	Time	Username	Problem	Language	Result	Execution time	Memory
307529		shivensinha4	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	1312 ms	87860 KiB

commuter_pass

#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXN = 1e5;
const ll INF = 1e15;
int n, m;
vector<pair<int, ll>> adj[MXN+1];
ll du[MXN+1], dv[MXN+1];
pair<ll, ll> df[MXN+1][3][3];

void dijk(int a, ll d[]) {
	for_(i, 0, n) d[i] = INF;
	d[a] = 0;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	pq.push({0, a});
	
	while (pq.size()) {
		int p = pq.top().second; ll dist = pq.top().first; pq.pop();
		if (d[p] < dist) continue;
		for (auto i: adj[p]) if (d[i.first] > dist+i.second) {
			d[i.first] = dist+i.second;
			pq.push({d[i.first], i.first});
		}
	}
}


int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int s, t, u, v; cin >> n >> m >> s >> t >> u >> v;
	s -= 1; t -= 1; u -= 1; v -= 1;
	for_(i, 0, m) {
		int a, b; ll w; cin >> a >> b >> w;
		a -= 1;  b -= 1;
		adj[a].push_back({b, w}); adj[b].push_back({a, w});
	}
	
	dijk(u, du); dijk(v, dv);
	
	for_(i, 0, n) {
		adj[i].push_back({i, 0});
		for_(j, 0, 2) for_(k, 0, 2) df[i][j][k] = {INF, INF};
	}
	
	priority_queue<pair<pair<ll, ll>, vi>, vector<pair<pair<ll, ll>, vi>>, greater<pair<pair<ll, ll>, vi>>> pq;
	pq.push({{0, 0}, {s, 0, 0}});
	
	ll ans = INF, bda = INF;
	while (pq.size()) {
		vi p = pq.top().second; 
		ll da = pq.top().first.first, db = pq.top().first.second; pq.pop();
		if (df[p[0]][p[1]][p[2]] < pair<ll, ll> {da, db}) continue;
		
		if (p == (vi) {t, 1, 1}) {
			if (da < bda) ans = db;
			else if (da == bda) ans = min(ans, db);
			bda = min(bda, da);
		}
		for (auto i: adj[p[0]]) {
			if (df[i.first][p[1]][p[2]] > pair<ll, ll> {da+i.second, db}) {
				df[i.first][p[1]][p[2]] = {da+i.second, db};
				pq.push({{da+i.second, db}, {i.first, p[1], p[2]}});
			}
			
			if (!p[1] and df[i.first][1][p[2]] > pair<ll, ll> {da+i.second, db+du[p[0]]}) {
				df[i.first][1][p[2]] = {da+i.second, db+du[p[0]]};
				pq.push({{da+i.second, db+du[p[0]]}, {i.first, 1, p[2]}});
			}
			
			if (!p[2] and df[i.first][p[1]][1] > pair<ll, ll> {da+i.second, db+dv[p[0]]}) {
				df[i.first][p[2]][1] = {da+i.second, db+dv[p[0]]};
				pq.push({{da+i.second, db+dv[p[0]]}, {i.first, p[1], 1}});
			}
		}
	}
	
	cout << min(ans, du[v]) << endl;

	return 0;
}

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