Submission #1210496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210496		witek_cpp	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	225 ms	24860 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;

#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define wczytaj(a, c, n) a.resize(n); f(i, c, n) cin >> a[i];
#define sz(a) int(a.size())
#define wypisz(a, c) f(i, c, sz(a)) cout << a[i] << " "; cout << "\n";

int n, m, s, t, u, v; //zerujemy wybrane z s do t

vector<vector<pair<int, ll>>> sasiedzi;

vector<vector<ll>> min_odl(4);
vector<ll> dp;
vector<ll> dp_tyl;
vector<int> odw;
vector<int> odw2;

void dijkstra(int ind, int zrodlo) {
	min_odl[ind].resize(n + 1);
	f(i, 1, n + 1) min_odl[ind][i] = -1;
	priority_queue<pair<ll, int>> kolejka;
	kolejka.push({0, zrodlo});
	pair<ll, int> p1;
	while (kolejka.size()) {
		p1 = kolejka.top();
		kolejka.pop();
		if (min_odl[ind][p1.nd] != -1) continue;
		p1.st = -p1.st;
		min_odl[ind][p1.nd] = p1.st;
		for (pair<int, ll> sasd: sasiedzi[p1.nd]) {
			if (min_odl[ind][sasd.st] != -1) continue;
			kolejka.push({-(p1.st + sasd.nd), sasd.st});
		}
	}
}

void dfs_dp(int w) { //mamy juz gwarancje ze lezy na najkrotszej sciezce z s do t
	odw[w] = 1;
	dp[w] = min_odl[1][w];
	for (pair<int, ll> sasd: sasiedzi[w]) {
		if ((min_odl[2][w] + sasd.nd + min_odl[3][sasd.st]) > min_odl[2][t]) continue; //krawedz nie lezy na najkrotszej sciezce
		if (!odw[sasd.st]) {
			dfs_dp(sasd.st);
		}
		dp[w] = min(dp[w], dp[sasd.st]);
	}
}

void dfs_od_tylu(int w) {
	dp_tyl[w] = min_odl[1][w];
	odw2[w] = 1;
	
	for (pair<int, ll> sasd: sasiedzi[w]) {
		if ((min_odl[3][w] + sasd.nd + min_odl[2][sasd.st]) > min_odl[3][s]) continue; //krawedz nie jest na minimalnej sciezce z t do s
		if (!odw2[sasd.st]) {
			dfs_od_tylu(sasd.st);
		}
		dp_tyl[w] = min(dp_tyl[w], dp_tyl[sasd.st]);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> s >> t >> u >> v;
	
	sasiedzi.resize(n + 1);
	
	int w1, w2;
	ll w3;
	
	f(i, 0, m) {
		cin >> w1 >> w2 >> w3;
		sasiedzi[w1].pb({w2, w3});
		sasiedzi[w2].pb({w1, w3});
	}
	
	dijkstra(0, u); dijkstra(1, v); dijkstra(2, s); dijkstra(3, t);
	dp.resize(n + 1, -1);
	dp_tyl.resize(n + 1, -1);
	odw.resize(n + 1, 0);
	odw2.resize(n + 1, 0);
	
	dfs_dp(s);
	dfs_od_tylu(t);
	
	ll wnk = min_odl[0][v];
	
	/*f(i, 1, n + 1) {
		cout << dp[i] << " ";
	}*/
	
	f(i, 1, n + 1) {
		if (dp[i] != -1) {
			wnk = min(wnk, min_odl[0][i] + min(dp_tyl[i], dp[i]));
		}
	}
	
	cout << wnk;
	
	return 0;
}

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