题解：P10206 [JOI 2024 Final] 建设工程 2 / Construction Project 2

#include<bits/stdc++.h>
#define int long long
#define double long double
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
int n,m;
int s,t,l,k;
struct node{
	int v,w;
};
vector<node>g[N];
int dis1[N],dis2[N];
bool vis1[N],vis2[N];
struct node2{
	int u,dis;
	bool operator>(const node2 &a)const{
		return dis>a.dis;
	}
};
priority_queue<node2,vector<node2>,greater<node2> >pq1,pq2;
void dij1(){//求dis1
	memset(dis1,0x3f,sizeof dis1);
	dis1[s]=0;
	pq1.push({s,0});
	while(pq1.size()){
		int u=pq1.top().u;
		pq1.pop();
		if(vis1[u]){
			continue;
		}
		vis1[u]=1;
		for(auto i:g[u]){
			int v=i.v,w=i.w;
			if(dis1[v]>dis1[u]+w){
				dis1[v]=dis1[u]+w;
				pq1.push({v,dis1[v]});
			}
		}
	}
	return ;
}
void dij2(){//求dis2
	memset(dis2,0x3f,sizeof dis2);
	dis2[t]=0;
	pq2.push({t,0});
	while(pq2.size()){
		int u=pq2.top().u;
		pq2.pop();
		if(vis2[u]){
			continue;
		}
		vis2[u]=1;
		for(auto i:g[u]){
			int v=i.v,w=i.w;
			if(dis2[v]>dis2[u]+w){
				dis2[v]=dis2[u]+w;
				pq2.push({v,dis2[v]});
			}
		}
	}
	return ;
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	cin>>s>>t>>l>>k;
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	dij1();
	dij2();
	if(dis1[t]<=k){
		cout<<n*(n-1)/2<<endl;
		return 0;
	}
	sort(dis1+1,dis1+1+n);
	int ans=0;
	for(int v=1;v<=n;v++){
		int tmp=k-l-dis2[v];//转换后的式子
		int lb=upper_bound(dis1+1,dis1+1+n,tmp)-dis1-1;//二分求答案
		ans+=lb;
	}
	cout<<ans<<endl;
	return 0;
}