Submission #96369

#	Time	Username	Problem	Language	Result	Execution time	Memory
96369		hugo_pm	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	518 ms	35284 KiB

commuter_pass

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

#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= b; --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second
#define BIG 1000000000000000000

typedef long long ll;
typedef long double ld;

void cpr(string s, vector<int> v)
{ int i = 0; for (char c : s) { if (c == '$') cout << v[i++]; else cout << c; } cout << '\n'; }

void cpr(string s) { cpr(s, {}); }

void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

const int borne = 101*1000;
int nbNod, nbLi;
int depri, arpri, dean, aran;
vector<pair<int,int>> adj[borne];
vector<int> pcc[borne];
int orig = 0;
vector<int> green[2][borne];

void rundij(int dep)
{
	vector<int> md(nbNod, -1);
	md[dep] = 0;
	priority_queue<pair<int, int>> dij;
	dij.push({0, dep});
	while (!dij.empty()) {
		int dist = -dij.top().fi, nod = dij.top().se;
		dij.pop();
		if (dist != md[nod]) continue;
		for (auto lien : adj[nod]) {
			int vo = lien.fi, poids = lien.se;
			int nd = dist+poids;
			if (md[vo] == -1 || nd < md[vo]) {
				md[vo] = nd;
				dij.push({-nd, vo});
			}
		}
	}
	form(i, nbNod) assert(md[i] != -1);
	pcc[dep] = md;
}

pair<int, int> nodtri[borne];

void comp()
{
	for (int nod = 0; nod < nbNod; ++nod) {
		nodtri[nod] = {pcc[dean][nod], nod};
		for (auto lien : adj[nod]) {
			int vo = lien.fi, poids = lien.se;
			int neworig = pcc[depri][nod] + poids + pcc[arpri][vo];
			int neworig2 = pcc[arpri][nod] + poids + pcc[depri][vo];
			if (neworig == orig) {
				green[0][nod].push_back(vo);
			}
			if (neworig2 == orig) {
				green[1][nod].push_back(vo);
			}
		}
	}
	sort(nodtri, nodtri+nbNod);
}

int tot = LLONG_MAX;
int mode = 0;
bool vu[2][borne];
int mku = 0;

void dfs(int nod)
{
	vu[mode][nod] = true;
	chmin(tot, mku + pcc[aran][nod]);
	for (int vo : green[mode][nod]) {
		if (! vu[mode][vo]) {
			dfs(vo);
		}
	}
}

void solve()
{
	cin >> nbNod >> nbLi;
	cin >> depri >> arpri;
	cin >> dean >> aran;
	--depri; --arpri; --dean; --aran;

	for (int ind = 0; ind < nbLi; ++ind) {
		int x, y, p;
		cin >> x >> y >> p;
		--x; --y;
		adj[x].push_back({y,p});
		adj[y].push_back({x,p});
	}

	rundij(depri);
	rundij(arpri);
	rundij(dean);
	rundij(aran);

	orig = pcc[depri][arpri];
	comp();

	for (; mode < 2; ++mode) {
		for (int i = 0; i < nbNod; ++i) {
			mku = nodtri[i].fi;
			int dep = nodtri[i].se;
			if (vu[mode][dep]) continue;
			dfs(dep);
		}
	}

	cout << tot << "\n";

}

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