Submission #1057342

#TimeUsernameProblemLanguageResultExecution timeMemory
1057342beaconmcConstruction Project 2 (JOI24_ho_t2)C++14
100 / 100
215 ms38832 KiB
#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;

const ll maxn = 200005;
const ll INF = 10000000000000000;
vector<array<ll, 2>> edges[maxn];
ll dists[maxn];
ll distt[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	FOR(i,0,maxn) dists[i] = INF, distt[i] = INF;

	ll n,m;
	cin >> n >> m;
	ll s, t, l, k;
	cin >> s >> t >> l >> k;
	FOR(i,0,m){
		ll a,b,c;
		cin >> a >> b >> c;

		edges[a].push_back({b,c});
		edges[b].push_back({a,c});
	}

	priority_queue<vector<ll>> pq;
	dists[s] = 0;
	pq.push({0, s});

	while (pq.size()){
		vector<ll> node = pq.top(); pq.pop();

		node[0] = -node[0];
		if (dists[node[1]] != node[0]) continue;

		for (auto&i : edges[node[1]]){
			if (dists[i[0]] > dists[node[1]] + i[1]){
				dists[i[0]] = dists[node[1]] + i[1];
				pq.push({-dists[i[0]] , i[0]});
			}
		}
	}
	distt[t] = 0;
	pq.push({0, t});

	while (pq.size()){
		vector<ll> node = pq.top(); pq.pop();

		node[0] = -node[0];
		if (distt[node[1]] != node[0]) continue;

		for (auto&i : edges[node[1]]){
			if (distt[i[0]] > distt[node[1]] + i[1]){
				distt[i[0]] = distt[node[1]] + i[1];
				pq.push({-distt[i[0]] , i[0]});
			}
		}
	}

	if (dists[t] <= k) cout << n * (n-1) / 2;
	else{
		ll ans = 0;
		vector<ll> S, T;
		FOR(i,1,n+1) S.push_back(dists[i]), T.push_back(distt[i]);
		sort(S.begin(), S.end());
		sort(T.begin(), T.end());


		FOR(i,0,n){
			ll req = k - (S[i]+l);
			ll sus = upper_bound(T.begin(), T.end(), req) - T.begin();
			ans += sus;
		}

		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...