Submission #1214201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214201		trimkus	Construction Project 2 (JOI24_ho_t2)	C++20	45 / 100	2091 ms	17600 KiB

Main

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


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	int s, t, l;
	ll k;
	cin >> s >> t >> l >> k;
	vector<vector<pair<int, int>>> adj(n + 1);
	for (int i = 0; i < m; ++i) {
		int a, b, w;
		cin >> a >> b >> w;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}
	auto dijikstra = [&](int st, vector<ll>& dist) -> void {
		priority_queue<array<ll, 2>> pq;
		pq.push({0, st});
		dist[st] = 0;
		while (pq.size()) {
			ll d = -pq.top()[0];
			int v = pq.top()[1];
			pq.pop();
			if (dist[v] != d) continue;
			for (auto& [u, w] : adj[v]) {
				if (dist[u] > dist[v] + w) {
					dist[u] = dist[v] + w;
					pq.push({-dist[u], u});
				}
			}
		}
	};
	const ll INF = 1e18;
	vector<ll> dist1(n + 1, INF), dist2(n + 1, INF);
	dijikstra(s, dist1);
	dijikstra(t, dist2);
	int res = 0;
	if (dist1[t] <= k) {
		cout << n * (n - 1) / 2 << "\n";
		return 0;
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (i == j) continue;
			ll total = min(dist1[j], l + dist1[i]) + dist2[j];
			//~ cout << i << " -> " << j << " = " << total << "\n";
			if (total <= k) {
				res += 1;
			}
		}
	}
	
	cout << res << "\n";
}

• Subtask 1: 0 / 8
• Subtask 2: 16 / 16
• Subtask 3: 29 / 29
• Subtask 4: 0 / 47