Submission #1149041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149041		Nomio	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	138 ms	22188 KiB

Main

#include<bits/stdc++.h>
#define s second
#define f first
#define plli pair<long long, int>
#define pill pair<int, long long>

using namespace std;
using ll = long long;

int n, m, s, t;
ll l, k;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> s >> t >> l >> k;
	s--, t--;
	vector<plli> adj[n]; 
	for(int i = 0; i < m; i++) {
		int a, b;
		ll c;
		cin >> a >> b >> c;
		a--, b--;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	priority_queue<plli, vector<plli>, greater<plli>> pq;
	vector<ll> dis(n, 1e18);
	dis[s] = 0;
	pq.push({0, s});
	while(!pq.empty()) {
		ll dist = pq.top().f;
		int a = pq.top().s;
		pq.pop();
		if(dist != dis[a]) continue;
		for(plli p : adj[a]) {
			ll c = p.s;
			int b = p.f;
			if(dist + c < dis[b]) {
				dis[b] = dist + c;
				pq.push({dis[b], b});
			}
		}	
	}
	if(dis[t] <= k) {
		cout << 1LL * n * (n - 1) / 2 << '\n';
		return 0;
	}
	vector<ll> dis1(n, 1e18);
	dis1[t] = 0;
	pq.push({0, t});
	while(!pq.empty()) {
		ll dist = pq.top().f;
		int a = pq.top().s;
		pq.pop();
		if(dist != dis1[a]) continue;
		for(plli p : adj[a]) {
			ll c = p.s;
			int b = p.f;
			if(dist + c < dis1[b]) {
				dis1[b] = dist + c;
				pq.push({dis1[b], b});
			}
		}	
	}
	sort(dis1.begin(), dis1.end());
	ll ans = 0;
	for(int i = 0; i < n; i++) {
		ans += max(0ll, ll(upper_bound(dis1.begin(), dis1.end(), k - l - dis[i]) - dis1.begin()));
	}
	cout << ans << '\n';
	return 0;
}

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