Submission #1325860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325860		csachy13	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2096 ms	54508 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

ll N, M, S, T, U, V;

vector<set<array<ll, 2>>> graph;
vector<array<ll, 3>> edges;

void path(ll node, vector<ll>* distances) {
	priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
	
	fill(distances->begin(), distances->end(), LLONG_MAX); (*distances)[node] = 0;
	pq.push({0, node});
	
	while (!pq.empty()) {
		auto [distance, front] = pq.top(); pq.pop();
		
		if ((*distances)[front] != distance) continue;
		for (auto [neighbor, weight] : graph[front]) {
			if ((*distances)[neighbor] > (*distances)[front] + weight) {
				(*distances)[neighbor] = (*distances)[front] + weight;
				pq.push({(*distances)[neighbor], neighbor});
			}
		}
	}
}

void dfs(ll node, vector<ll>* dp, vector<ll>* dist, vector<set<ll>>* g) {
	// cout << node << "<- cur node\n";
	(*dp)[node] = (*dist)[node];
	for (ll neighbor : (*g)[node]) {
		// cout << "-->going to " << neighbor << '\n';
		
		dfs(neighbor, dp, dist, g);
		
		(*dp)[node] = min((*dp)[neighbor], (*dp)[node]);
	}
}
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0); 
	
	cin >> N >> M;
	cin >> S >> T >> U >> V; S--; T--; U--; V--;
	
	graph.resize(N);
	vector<ll> dS(N), dT(N), dU(N), dV(N);
	
	for (int i=0; i<M; i++) {
		ll A, B, C; cin >> A >> B >> C; A--; B--;
		graph[A].insert({B, C}); graph[B].insert({A, C});
		edges.push_back({A, B, C});
	}
	
	path(S, &dS); path(T, &dT); path(U, &dU); path(V, &dV);
	
	vector<set<ll>> graph_s(N), graph_t(N);
	
	for (int i=0; i<M; i++) {
		auto [from, to, weight] = edges[i];
		
		if (dS[from] + weight + dT[to] == dS[T]) {
			graph_s[from].insert(to);
			graph_t[to].insert(from);
		}
		
		if (dT[from] + weight + dS[to] == dT[S]) {
			graph_s[to].insert(from);
			graph_t[from].insert(to);
		}
	}
	
	vector<ll> dp_s(N, LLONG_MAX/3), dp_t(N, LLONG_MAX/3), dist;
	
	dfs(S, &dp_s, &dU, &graph_s);
	dfs(T, &dp_t, &dU, &graph_t);
	
	ll Res = LLONG_MAX;
	for (int i=0; i<N; i++) {
		Res = min(Res, min(dp_s[i] + dV[i], dp_t[i] + dV[i]));
	}
	
	cout << Res << '\n';
	
	
	
	
	
	
	
	
	
	return 0;
}

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