题解：P10193 [USACO24FEB] Bessla Motors G

· · 题解

很考察对 dijkstra 算法流程理解程度的一道题。

注意到 k 并不大，因此考虑一些和 k 相关的做法。

先从特殊情况入手，如果 k=1 那就是对每个点判断离它最近的关键点距离它是否不超过 r，这是个经典的多源最短路问题，只需要将每个关键点的初始 \rm dis 设为 0 仍进堆里跑 dijkstra 就能求出。你也可以理解为建了一个向所有关键点连了 0 权边的超级源点，以这个超级源点为源跑最短路。

对于 k>1，考虑魔改下 dijkstra，我们对于堆内的每个结点额外记录下这条路径初始是从哪个关键点走来的，更新结点时记录 k 个来自不同关键点的最短路即可，这部分语言描述有点抽象，直接看代码会非常好理解。

对正确性的简要证明：思考 dijkstra 的算法流程，我们每次从堆顶取出来的一定是路径最短的点，因此每个点取出来的 k 种不同源点的路径一定是最短的。

对复杂度的简要证明：同样因为每次在堆顶取出来的是最短路，所以每个点至多被取出来向周围扩展 k 次，复杂度 O(km\log n)。

当然我懒得实现精细了，用 multiset 代替了堆，同时记录不同的源点路径用的是 map，可能会稍劣一些。

#include<bits/stdc++.h>
//#define int long long
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Rof(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
using PII = pair<int, int>;
const int N = 5e5 + 5;
int n, m, c, k, r;
vector<PII> G[N];
map<int, bool> vis[N];
struct node{int id, dis, pre;};
bool operator<(const node &a, const node &b){
    return a.dis < b.dis;
}
void dijkstra(){
    multiset<node> st;
    For(i, 1, c) st.insert({i, 0, i});
    while(!st.empty()){
        auto [now, dis, pre] = *st.begin();
        st.erase(st.begin());
        if(vis[now].size() >= k || vis[now].count(pre)) continue;
        vis[now][pre] = 1;
        for(auto [to, val] : G[now]){
            int newd = dis + val;
            if(newd > r || vis[to].size() >= k || vis[to].count(pre)) continue;
            st.insert({to, newd, pre});
        }
    }
}
void Solve(){
    cin >> n >> m >> c >> r >> k;
    For(i, 1, m){
        int u, v, w; cin >> u >> v >> w;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    dijkstra();
    vector<int> vec;
    For(i, c + 1, n) if(vis[i].size() >= k)
        vec.emplace_back(i);
    cout << vec.size() << '\n';
    for(int to : vec) cout << to << '\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T = 1; //cin >> T;
    while(T--) Solve();
    return 0;
}