#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
struct st
{
int u,w;
bool operator < (const st&o) const
{
return w>o.w;
}
};
map<pair<int,int>,int> mp;
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin>>n>>m;
int ss,tt,l,k;
cin>>ss>>tt>>l>>k;
vector<pair<int,int>> ad[n+1];
for(int i=0;i<m;i++)
{
int u,v,w;
cin>>u>>v>>w;
ad[u].push_back({v,w});
ad[v].push_back({u,w});
if(u>v)
swap(u,v);
mp[{u,v}]=w;
}
pair<int,int> dists[n+1],distt[n+1];
for(int i=1;i<=n;i++)
{
dists[i]={i,LLONG_MAX};
distt[i]={i,LLONG_MAX};
}
dists[ss].s=0;
distt[tt].s=0;
priority_queue<st> q;
q.push({ss,0});
while(!q.empty())
{
auto p=q.top();
q.pop();
int u=p.u,w=p.w;
if(dists[u].s<w)
continue;
for(auto x:ad[u])
{
if(dists[x.f].s>w+x.s)
{
dists[x.f].s=w+x.s;
q.push({x.f,w+x.s});
}
}
}
q.push({tt,0});
while(!q.empty())
{
auto p=q.top();
q.pop();
int u=p.u,w=p.w;
if(distt[u].s<w)
continue;
for(auto x:ad[u])
{
if(distt[x.f].s>w+x.s)
{
distt[x.f].s=w+x.s;
q.push({x.f,w+x.s});
}
}
}
sort(dists+1,dists+n+1,[](auto &x,auto &y)
{
return x.s<y.s;;
});
sort(distt+1,distt+n+1,[](auto &x,auto &y)
{
return x.s<y.s;;
});
int ans=0;
set<int> sss;
for(int i=1;i<=n;i++)
sss.insert(i);
deque<int> dq;
int dist[n+1];
for(int i=1;i<=n;i++)
{
dq.push_back(distt[i].f);
dist[distt[i].f]=distt[i].s;
}
if(dists[tt].s<=k)
{
cout<<(n*(n-1))/2;
return 0;
}
for(int i=1;i<=n;i++)
{
while(!dq.empty()&&dists[i].f+l+dist[dq.back()]>k)
{
sss.erase(dq.back());
dq.pop_back();
}
sss.erase(dists[i].f);
ans+=sss.size();
}
/*int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int sp=LLONG_MAX;
int ll=LLONG_MAX;
if(dists[i].s!=ll&&distt[j].s!=ll)
{
sp=dists[i].s+distt[j].s+l;
//if(mp[{i,j}]!=0)
//sp=min(sp,dists[i].s+distt[j].s+mp[{i,j}]);
}
if(distt[i].s!=ll&&dists[j].s!=ll)
{
sp=min(sp,distt[i].s+dists[j].s+l);
//if(mp[{i,j}]!=0)
//sp=min(sp,distt[i].s+dists[j].s+mp[{i,j}]);
}
if(sp<=k)
ans++;
else if(dists[tt].s<=k)
ans++;
}
}*/
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |