Submission #1341105

#TimeUsernameProblemLanguageResultExecution timeMemory
1341105JuanJLConstruction Project 2 (JOI24_ho_t2)C++20
100 / 100
606 ms31360 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)
#define mset(a,v) memset(a,v,sizeof(a))

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template< typename T >
using iset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

ll actualres(multiset<ll> &s){
	ll mini = *s.begin();
	ll maxi = *(--s.end());
	ll res = maxi-mini;
	return res;
}

const int MAXN = 200000+5;

vector<pair<ll,ll>> adj[MAXN];

ll n;
bool vis[MAXN];

vector<ll> dijkstra(ll ini){
	vector<ll> dist(n,10000000000000000);

	dist[ini]=0;
	priority_queue<pair<ll,ll>> pq; pq.push({0,ini});

	while(!pq.empty()){
		ll nd = pq.top().snd;
		ll cost = pq.top().fst*-1;
		pq.pop();
		vis[nd]=true;
		

		if(dist[nd]!=cost) continue;

		for(auto i:adj[nd]){
			if(dist[i.fst]==-1 || dist[i.fst]>cost+i.snd){
				dist[i.fst]=cost+i.snd;
				pq.push({dist[i.fst]*-1,i.fst});
			}
		}
	}

	return dist;
}

int main(){
	ll m; 
	ll s,t,l,k; 
	cin>>n>>m;
	cin>>s>>t>>l>>k; s--; t--;

	ll u,v,c; 
	forn(i,0,m){
		cin>>u>>v>>c; u--; v--;
		adj[u].pb({v,c});
		adj[v].pb({u,c});
	}

	vector<ll> Sto = dijkstra(s);
	vector<ll> Tto = dijkstra(t);


	if(Sto[t]<=k) cout<<(n*(n-1))/2<<'\n';
	else{
		iset<pair<ll,ll>> Ttoms;

		forn(i,0,n) Ttoms.insert({Tto[i],i});

		ll res = 0;
		forn(i,0,n){
			Ttoms.erase(Ttoms.find({Tto[i],i}));
	
			//cout<<Sto[i]<<" "<<l<<'\n';
			ll obj = k-(Sto[i]+l);
			//cout<<i<<" -> "<<obj<<" "<<Ttoms.order_of_key({obj,5*n})<<'\n';
			res+=Ttoms.order_of_key({obj,5*n});
		}

		iset<pair<ll,ll>> Stoms;
		forn(i,0,n) Stoms.insert({Sto[i],i});

		
		forn(i,0,n){
			Stoms.erase(Stoms.find({Sto[i],i}));
				
						//cout<<Sto[i]<<" "<<l<<'\n';
			ll obj = k-(Tto[i]+l);
						//cout<<i<<" -> "<<obj<<" "<<Ttoms.order_of_key({obj,5*n})<<'\n';
			res+=Stoms.order_of_key({obj,5*n});
		}
		cout<<res<<'\n';
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...