제출 #1328063

#제출 시각아이디문제언어결과실행 시간메모리
1328063viduxConstruction Project 2 (JOI24_ho_t2)C++17
100 / 100
144 ms24892 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n, m; cin >> n >> m;
	ll s, t, l, k; cin >> s >> t >> l >> k;
	s--, t--;
	vector<vector<pll>> adj(n);
	for (int i = 0; i < m; i++) {
		ll u, v, w; cin >> u >> v >> w;
		u--, v--;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	auto sssp = [&](int u) -> vector<ll> {
		vector<ll> dist(n, 1e18);
		dist[u] = 0;
		priority_queue<pll, vector<pll>, greater<pll>> pq;
		pq.push({0, u});
		while (pq.size()) {
			auto [d, v] = pq.top(); pq.pop();
			if (d != dist[v]) continue;
			for (auto [vv, w] : adj[v]) {
				ll nd = d+w;
				if (nd < dist[vv]) {
					dist[vv] = nd;
					pq.push({nd, vv});
				}
			}
		}
		return dist;
	};
	vector<ll> dists = sssp(s), distt = sssp(t);
	if (dists[t] <= k) {
		cout << n*(n-1)/2 << endl;
		return 0;
	}
	sort(distt.begin(), distt.end());
	ll ans = 0;
	for (ll d1 : dists) {
		ll d = d1+l;
		if (d > k) continue;
		ll mx = k-d;
		ll i = upper_bound(distt.begin(), distt.end(), mx)-distt.begin();
		ans += i;
	}
	cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...