yen算法求k短路c++模板

以下是C++实现的Yen算法求k短路的模板代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
const int MAXM = 200005;
const int INF = 0x3f3f3f3f;

int n, m, k, dis[MAXN], vis[MAXN], cnt;
int head[MAXN], nxt[MAXM], ver[MAXM], edge[MAXM];
int ans[MAXN];

struct Node {
    int dis, id;
    bool operator < (const Node& nd) const {
        return dis > nd.dis;
    }
};

struct Edge {
    int u, v, w;
} e[MAXM];

priority_queue <Node> q;
vector <int> vec[MAXN];

void add(int u, int v, int w) {
    ver[++cnt] = v;
    edge[cnt] = w;
    nxt[cnt] = head[u];
    head[u] = cnt;
}

void dijkstra(int s) {
    memset(vis, 0, sizeof(vis));
    memset(dis, INF, sizeof(dis));
    dis[s] = 0;
    q.push((Node){0, s});
    while (!q.empty()) {
        Node t = q.top();
        q.pop();
        int u = t.id;
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = nxt[i]) {
            int v = ver[i], w = edge[i];
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) q.push((Node){dis[v], v});
            }
        }
    }
}

void init() {
    cnt = 0;
    memset(head, 0, sizeof(head));
}

void Yen(int s, int t) {
    dijkstra(s);
    if (dis[t] == INF) return;
    priority_queue <Node> pq;
    pq.push((Node){dis[t], t});
    for (int i = 1; i <= k; ++i) {
        if (pq.empty()) break;
        int u = pq.top().id;
        pq.pop();
        ans[i] = dis[u];
        for (int j = 1; j <= n; ++j) vec[j].clear();
        for (int j = head[u]; j; j = nxt[j]) vec[ver[j]].push_back(j);
        for (int p = 1; p <= i; ++p) {
            int d = ans[p], v = e[p].u, w = e[p].w;
            for (int j = 0; j < vec[v].size(); ++j) {
                int k = vec[v][j];
                if (k == w) continue;
                if (p == 1 && j == 0) continue;
                int tmp = dis[ver[k]];
                dis[ver[k]] = d + edge[k] - dis[v] + dis[ver[k]];
                e[p].u = ver[k], e[p].w = k;
                pq.push((Node){dis[ver[k]] + ans[p - 1], ver[k]});
                if (p == k) ans[p] = dis[t];
            }
            e[p].u = v, e[p].w = w;
            memcpy(head, nxt, sizeof(nxt));
        }
    }
    for (int i = 1; i <= k; ++i) printf("%d ", ans[i]);
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    init();
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    Yen(1, n);
    return 0;
}

其中，`n`表示节点数量，`m`表示边的数量，`k`表示要求的第k短路。

在代码中，我们首先使用Dijkstra算法求出源点到终点的最短路`dis`，然后使用优先队列`pq`存储当前的最短路，对于每一次迭代，我们从`pq`中取出距离终点最近的节点`u`，然后枚举所有与`u`相邻的边，计算新的路径长度，并将其插入`pq`中。最后，我们将前`k`个短路的长度存储在`ans`数组中输出即可。

需要注意的是，在每一次迭代之后，我们需要将邻接表`head`恢复成初始状态，否则会影响后续的计算。同时，在计算新的路径长度时，需要注意避免重复计算，具体实现见代码注释。