Submission #1145551

#TimeUsernameProblemLanguageResultExecution timeMemory
1145551ezzzayConstruction Project 2 (JOI24_ho_t2)C++20
0 / 100
2096 ms22972 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int a[N];
vector<pair<int,int>>v[N];
int dst[2][N];
void djk(int x, int s){
	priority_queue<pair<int,int>>q;
	for(int i=0;i<N;i++){
		dst[x][i]=1e17;
	}
	dst[x][s]=0;
	q.push({0,s});
	while(!q.empty()){
		int w= -q.top().ff;
		int a=q.top().ss;
		q.pop();
		if(w>dst[x][a])continue;
		for(auto p:v[a]){
			int b=p.ff;
			int c=p.ss;
			if(dst[x][b] > dst[x][a]+c){
				dst[x][b]=dst[x][a]+c;
				q.push({-dst[x][b],b});
			}
		}
	}
}
signed main(){
	int n,m,s,t,l,k;
	cin>>n>>m>>s>>t>>l>>k;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		v[a].pb({b,c});
		v[b].pb({a,c});
	}
	djk(0,s);
	djk(1,t);
	if(dst[0][t]<=l){
		cout<<(n-1)*n/2;
		return 0;
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			if(dst[0][i] + dst[1][j]+l <=k)ans++;
		}
	}
	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...