Submission #1322653

#TimeUsernameProblemLanguageResultExecution timeMemory
1322653exoworldgdConstruction Project 2 (JOI24_ho_t2)C++20
100 / 100
191 ms24892 KiB
#include<bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
#define int long long
#define P array<int,2>
using namespace std;
const int INF=1e18;
int n,m,s,t,l,k,ans,d1[200005],d2[200005];
vector<P>g[200005];
void f(int st,int*d){
	priority_queue<P,vector<P>,greater<>>pq;
	for(int i=0;i<n;i++)d[i]=1e18;
	d[st]=0,pq.push({0,st});
	while(pq.size()){
		auto[di,u]=pq.top();pq.pop();
		if(di<=d[u])for(auto[v,w]:g[u])if(d[u]+w<d[v])d[v]=d[u]+w,pq.push({d[v],v});
	}
}
signed main(void){
	exoworldgd;
	cin>>n>>m>>s>>t>>l>>k,s--,t--;
	for(int i=0,a,b,c;i<m;i++)cin>>a>>b>>c,a--,b--,g[a].push_back({b,c}),g[b].push_back({a,c});
	f(s,d1),f(t,d2);
	if(d1[t]<=k){cout<<n*(n-1)/2;return 0;}
	sort(d1,d1+n),sort(d2,d2+n);
	for(int i=0,j=n-1;i<n;i++){
		while(j+1&&d1[i]+d2[j]+l>k)j--;
		ans+=j+1;
	}
	cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...