Submission #388676

#	Time	Username	Problem	Language	Result	Execution time	Memory
388676		Vlatko	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	534 ms	25588 KiB

commuter_pass

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

using ll = long long;
using pli = pair<ll, int>;

const ll inf = 1e18;
const int N = 100100;

int n, m, S, T, U, V;
vector<pli> adj[N];
ll ans;
ll dU[N];
ll dV[N];
ll dS[N];
vector<int> adj2[N];
bool vis[N];

void dijkstra(int source, ll dist[N]) {
	priority_queue<pli, vector<pli>, greater<pli>> pq;
	for (int i = 1; i <= n; ++i) {
		dist[i] = inf;
	}
	dist[source] = 0;
	pq.emplace(0, source);
	while (!pq.empty()) {
		ll d, w;
		int u, v;
		tie(d, u) = pq.top();
		pq.pop();
		if (d != dist[u]) continue;
		for (pli to : adj[u]) {
			tie(w, v) = to;
			if (d + w < dist[v]) {
				dist[v] = d + w;
				pq.emplace(dist[v], v);
			}
		}
	}
}

bool dfs(int u, ll mdU, ll mdV) {
	vis[u] = true;
	mdU = min(mdU, dU[u]);
	mdV = min(mdV, dV[u]);
	bool canReachT = (u == T);
	if (u != T) {
		for (int v : adj2[u]) {
			if (!vis[v]) {
				if (dfs(v, mdU, mdV)) {
					canReachT = true;
				}
			}
		}
	}
	if (canReachT) {
		ans = min(ans, mdU + dV[u]);
		ans = min(ans, mdV + dU[u]);
//		cout<<"x="<<mindUnode<<"("<<mindU<<") y="<<u<<"("<<dV[u]<<") res="<<mindU+dV[u]<<"\n";
	}
	return canReachT;
}

void print(ll d[N], string s) {
	cout << s << ":\n";
	for (int i = 1; i <= n; ++i) {
		cout << " " << i << ": " << d[i] << "\n";
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
//	#ifndef _DEBUG
//	freopen("piepie.in", "r", stdin);
//	freopen("piepie.out", "w", stdout);
//	#endif
	cin >> n >> m >> S >> T >> U >> V;
	for (int i = 0; i < m; ++i) {
		int a, b, w;
		cin >> a >> b >> w;
		adj[a].emplace_back(w, b);
		adj[b].emplace_back(w, a);
	}
	dijkstra(U, dU);
	dijkstra(V, dV);
	dijkstra(S, dS);
//	cout<<"U="<<U<<", "; print(dU, "dU");
//	cout<<"V="<<V<<", "; print(dV, "dV");
//	cout<<"S="<<S<<", "; print(dS, "dS");
//	cout<<"T="<<T<<"\n";
	ans = min(dU[V], dV[U]);
	for (int u = 1; u <= n; ++u) {
		for (pli to : adj[u]) {
			if (dS[u] + to.first == dS[to.second]) {
				adj2[u].push_back(to.second);
//				cout << "adj2: " << u << " -> " << to.second << "\n";
			}
		}
		vis[u] = false;
	}
	dfs(S, inf, inf);
	cout << ans << '\n';
}

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