1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,l;
long long k;//不开 long long……
vector<pair<int,int>> road[200005];
long long dis1[200005],dis2[200005];
bool qd[200005];
void dij1(int from){
memset(qd,0,sizeof(qd));
memset(dis1,0x3f,sizeof(dis1));
dis1[from]=0;
qd[from]=1;
priority_queue<pair<unsigned long long,int>,vector<pair<unsigned long long,int>>,greater<pair<unsigned long long,int>>> pq;
for(pair<int,int> i:road[from]) pq.push(make_pair(i.second,i.first)),dis1[i.first]=i.second;
for(int i=1;i<n;i++){
pair<long long,int>t;
do{
if(pq.empty())return;
t=pq.top();
pq.pop();
}while(qd[t.second]);
qd[t.second]=1;
for(pair<int,int>add:road[t.second]){
if(!qd[add.first]){
if(dis1[add.first]>dis1[t.second]+add.second){
dis1[add.first]=dis1[t.second]+add.second;
pq.push(make_pair(dis1[add.first],add.first));
}
}
}
}
}
void dij2(int from){//这里写两个 Dijsktra 是因为数组传参比较麻烦
memset(qd,0,sizeof(qd));
memset(dis2,0x3f,sizeof(dis2));
dis2[from]=0;
qd[from]=1;
priority_queue<pair<unsigned long long,int>,vector<pair<unsigned long long,int>>,greater<pair<unsigned long long,int>>> pq;
for(pair<int,int> i:road[from]) pq.push(make_pair(i.second,i.first)),dis2[i.first]=i.second;
for(int i=1;i<n;i++){
pair<long long,int>t;
do{
if(pq.empty())return;
t=pq.top();
pq.pop();
}while(qd[t.second]);
qd[t.second]=1;
for(pair<int,int>add:road[t.second]){
if(!qd[add.first]){
if(dis2[add.first]>dis2[t.second]+add.second){
dis2[add.first]=dis2[t.second]+add.second;
pq.push(make_pair(dis2[add.first],add.first));
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
scanf("%d%d%d%lld",&s,&t,&l,&k);
for(int i=0;i<m;i++){
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
road[a].push_back(make_pair(b,w));
road[b].push_back(make_pair(a,w)); //读入时终点在前权值在后，跑最短路时权值在前终点在后
}
dij1(s);
if(dis1[t]<=k){
printf("%lld",(long long)n*(n-1)/2);//特判
}else{
dij2(t);
sort(dis2+1,dis2+n+1);
unsigned long long ans=0;
for(int i=1;i<=n;i++){
ans+=(((upper_bound(dis2+1,dis2+n+1,(long long)k-l-dis1[i])-dis2))-1);//二分查答案
}
printf("%llu",ans);
}
return 0;
}
|