题目大意
对于每个充电站找它所能去到的非充电站的点
T
T
T（$ C<T$ 同时两点的距离在
R
R
R 之内）。
然后对点
T
T
T进行统计，看共有多少不同的充电站经过它（设达成条件的充电站个数为
x
x
x）。
对于每个 x x x：
如果有 K ≤ x K\leq x K≤x 则该点被计入答案
分析
这道题直接跑全源最短路（
J
o
h
n
s
o
n
Johnson
Johnson）。
用
J
o
h
n
s
o
n
Johnson
Johnson 的时间复杂度为
O
(
N
M
log
M
)
O(NM\log M)
O(NMlogM)。
分两类，从充电站跑和从非充电站跑。
由于数据很水所以卡一下数据就能过。
Code
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+100;
const int MAXM=1e5+100;
const int inf=2147483647;
int n,m,c,r,k,cnt,sum,d[MAXN],hd[MAXM*2],nxt[MAXM*2],to[MAXM*2],val[MAXM*2],bz[MAXN];
bool vis[MAXN];
inline void myswap(int &x,int &y){int t=x;x=y;y=t;}
inline void add(int u,int v,int l)
{
to[++cnt]=v;
val[cnt]=l;
nxt[cnt]=hd[u];
hd[u]=cnt;
}
struct heap
{
int q[MAXN],id[MAXN],len;
inline void init(){len=0;}
inline void push(int x,int iid)
{
len++;
q[len]=x;
id[len]=iid;
int p=len;
while(p/2&&q[p/2]>q[p])
{
myswap(q[p/2],q[p]);
myswap(id[p/2],id[p]);
p/=2;
}
}
inline int getmin(){return id[1];}
inline void pop()
{
id[1]=id[len];
q[1]=q[len--];
int p=1;
while(p*2<=len)
{
int son=p*2;
if(son+1<=len&&q[son+1]<q[son]) son++;
if(q[p]<q[son]) break;
myswap(q[son],q[p]);
myswap(id[son],id[p]);
p=son;
}
}
inline bool empty(){return len>0?false:true;}
}hp;
inline void Dijkstra(int s)
{
hp.init();
int res=inf;
for(int i=1;i<=n;i++) d[i]=inf,vis[i]=false;
hp.push(0,s);
d[s]=0;
while(!hp.empty())
{
int x=hp.getmin();
hp.pop();
if(vis[x]) continue ;
if(!vis[x]&&x>c)
{
bz[x]++;
if(bz[x]==k) sum++;
}
vis[x]=true;
for(int i=hd[x];i;i=nxt[i])
{
int v=to[i],l=val[i];
if(d[v]>d[x]+l&&d[x]+l<=r)
{
d[v]=d[x]+l;
if(!vis[v]) hp.push(d[v],v);
}
}
}
}
inline void Dijkstra2(int s)
{
hp.init();
int res=inf;
for(int i=1;i<=n;i++) d[i]=inf,vis[i]=false;
hp.push(0,s);
d[s]=0;
while(!hp.empty())
{
int x=hp.getmin();
hp.pop();
if(vis[x]) continue ;
vis[x]=true;
for(int i=hd[x];i;i=nxt[i])
{
int v=to[i],l=val[i];
if(d[v]>d[x]+l&&d[x]+l<=r)
{
d[v]=d[x]+l;
if(v<=c) bz[s]++;
if(bz[s]==k)
{
sum++;
break;
}
if(!vis[v]) hp.push(d[v],v);
}
}
if(bz[s]==k) break;
}
}
int main()
{
// freopen("bm.in","r",stdin);
// freopen("bm.out","w",stdout);
scanf("%d%d%d%d%d",&n,&m,&c,&r,&k);
for(int i=1;i<=m;i++)
{
int u,v,l;
scanf("%d%d%d",&u,&v,&l);
add(u,v,l),add(v,u,l);
}
if(c<=10000) for(int i=1;i<=c;i++)
{
Dijkstra(i);
}
else for(int i=c+1;i<=n;i++)
{
Dijkstra2(i);
}
printf("%d\n",sum);
for(int i=c+1;i<=n;i++) if(bz[i]>=k) printf("%d\n",i);
return 0;
}