/* * @Author: RMQuan * @Date: 2025-10-27 21:21:38 * @Last Modified by: RMQuan * @Last Modified time: 2025-10-27 22:27:06 */ /*idea : */ #include <bits/stdc++.h> bool M1; #define int long long #define ll long long #define INTMAX INT_MAX #define INTMIN INT_MIN #define LONGMAX LLONG_MAX #define LONGMIN LLONG_MIN #define fi first #define se second #define memfull(a,b) memset(a,b,sizeof(a)); #define endl '\n' #define TASK "TEST" #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);} using namespace std; const int MOD=1e9+7; const int maxn=2e5+7; const int inf=1e18; vector<pair<int,int> > adj[maxn]; int n,m,S,T,L,K; int dis[maxn][2]; bool vst[maxn][2]; void dij(int s,int type) { priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; for (int i=1;i<=n;i++)dis[i][type]=inf; dis[s][type]=0; q.push({0,s}); while (q.size()) { int u=q.top().se; q.pop(); if (vst[u][type])continue; vst[u][type]=true; for (auto v:adj[u]) { if (dis[v.fi][type]>dis[u][type]+v.se) { dis[v.fi][type]=dis[u][type]+v.se; q.push({dis[v.fi][type],v.fi}); } } } } bool cmp1(int x,int y) { return dis[x][0]<dis[y][0]; } bool cmp2(int x,int y) { return dis[x][1]<dis[y][1]; } bool cmp3(int x,int y) { return dis[x][0]-dis[x][1]<dis[y][0]-dis[y][1]; } struct BIT { int N; vector<int> bit; BIT(int n):N(n),bit(n+5,0){} void upd(int x,int val) { for (;x<=N;x+=(x&-x))bit[x]+=val; } int get(int x) { int sum=0; for (;x>0;x&=(x-1))sum+=bit[x]; return sum; } }; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); file(); cin>>n>>m>>S>>T>>L>>K; for (int i=1;i<=m;i++) { int x,y,w; cin>>x>>y>>w; adj[x].push_back({y,w}); adj[y].push_back({x,w}); } dij(S,0); dij(T,1); vector<int> node; for (int i=1;i<=n;i++)node.push_back(i); sort(node.begin(),node.end(),cmp3); vector<int> nen; nen.push_back(-1e18); if (dis[T][0]<=K) { cout<<n*(n-1)/2; return 0; } for (int i=1;i<=n;i++) { nen.push_back(dis[i][0]); nen.push_back(K-L-dis[i][1]); nen.push_back(dis[i][1]); nen.push_back(K-L-dis[i][0]); } sort(nen.begin(),nen.end()); nen.erase(unique(nen.begin(),nen.end()),nen.end()); BIT bit(nen.size()+5); int ans=0; for (auto i:node) { ans+=bit.get(lower_bound(nen.begin(),nen.end(),K-L-dis[i][1])-nen.begin()); bit.upd(lower_bound(nen.begin(),nen.end(),dis[i][0])-nen.begin(),1); } cout<<ans; bool M2; cerr<<"-------------------------------------------------"<<endl; cerr<<"Time : "<<clock()<<" ms"<<endl; cerr<<"Memory : "<<abs(&M2-&M1)/1024/1024<<" MB"<<endl; cerr<<"-------------------------------------------------"<<endl; return 0; }

Main.cpp: In function 'int32_t main()':
Main.cpp:25:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:89:5: note: in expansion of macro 'file'
   89 |     file();
      |     ^~~~
Main.cpp:25:81: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:89:5: note: in expansion of macro 'file'
   89 |     file();
      |     ^~~~