题解：P10193 [USACO24FEB] Bessla Motors G

考虑一种特殊情况，若 K=1，则只需判断所有目的地是否能被至少一个充电站到达。

加入虚拟源点，向所有充电站连长为 0 的边，然后从虚拟源点开始求最短路，则所有 \operatorname{dist}[i] \leq R 的 i 都可达。

那如果 K>1 呢？由于 K 很小，我们考虑将每个 i 拆点，变为 (i,s_1),(i,s_2),....,(i,s_k)，用 \operatorname{dist}[(i,s_1)] 表示从 s_1 这个充电站出发，到达 i 的最短路。

这样，我们在堆顶取出一个 (u,s)，就可以更新所有的 \operatorname{dist}[(j,s)](存在边 u \to j)。

而如果在某一时刻，已经有 K 个充电站到 j 的距离小于等于 R，则接下来不再用 u 更新 j，以此保证总点数是 O(nK)。

这可以证明是对的：

1. 首先，j 已经满足条件，一定会被记入答案，j 不需要再被更新。
2. 根据 Dijkstra 的性质，先求出的一定是最短路，所以现在已有的 K 个 (j,s) 一定是到 j 距离最短的前 K 个充电站。 那么，若存在边 j \to v，且 K 个 (j,s) 都能更新 v，则 v 就直接满足条件；若有些 (j,s) 不能更新 v，那么我们少记入的那些 (j,s) 就更不能更新 v 了，因为他们长度更长。因此 j 更新其他点不受影响。

时间复杂度 O(Kn\log m)。

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5,M=2e5+5;

int n,m,C,R,K;
int h[N],e[M],ne[M],w[M],idx;
unordered_map<int,bool> start[N];
struct Node{
    int dist,ver,stid;
    bool operator< (const Node &t)const{
        return dist>t.dist;
    }
};

void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void dijkstra(){
    priority_queue<Node> q;
    for(int i=1; i<=C; i++) q.push({0,i,i});
    while(q.size()){
        auto t=q.top();
        q.pop();
        int u=t.ver,d=t.dist,s=t.stid;
        if(start[u][s]) continue; //如果(u,s)已被更新过，则当前的一定不优
        start[u][s]=1;
        for(int i=h[u]; ~i; i=ne[i]){
            int j=e[i];
            if(d+w[i]>R||start[j].size()>=K) continue;
            q.push({d+w[i],j,s});
        }
    }
}

int main(){
    memset(h,-1,sizeof h);
    scanf("%d%d%d%d%d",&n,&m,&C,&R,&K);
    for(int i=1; i<=m; i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }

    dijkstra();

    vector<int> res;
    for(int i=C+1; i<=n; i++)
        if(start[i].size()>=K)
            res.push_back(i);
    printf("%d\n",res.size());
    for(int t:res) printf("%d\n",t);

    return 0;
}