\(k\) 短路

这玩意据说可以用 A* 搞，或者用什么可持久化堆或者左偏树维护最短路树？
笔者不才，只好用分层图套 dijkstra 写一下。
思路来自这里。
大体流程：把一个点拆成 \(k\) 个（其实就是在 dis 数组加一维），对于一条边 \(<u,v>\)，可以从 \(u\) 的层数开始找能更新的 \(v\) 的第几层，然后挨个继承上一层，最后把 \(u\) 能更新的更新了。
核心代码：

for (int i = hd[u]; i; i = nt[i])
{
    int v = ed[i];
    int w = co[i] + d;
    int p = -1;
    for (int d = l; d < k; d++)
    {
        if (dis[v][d] > w)
        {
            p = d;
            break;
        }
        // 如果是要求严格第 k 短，则需要加上下面这两句话：
        else if (dis[v][k] == w)
            break;
    }
    if (p != -1)
    {
        for (int d = k - 1; d > p; d--)
        {
            if (dis[v][d - 1] == 0x3f3f3f3f)
                continue;
            dis[v][d] = dis[v][d - 1];
            pq.push ({dis[v][d], d, v});
        }
        dis[v][p] = w;
        pq.push ({w, p, v});
    }
}

例题：
bxgzoj 040306 内部 oj。

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 810, M = 8010, K = 45;
int n, m, k, ans;
int hd[N], ed[M], nt[M], co[M], cnt;
int dis[N][K];
bool vis[N][K];

struct node
{
    int d, l, u;
    bool operator <(const node a) const
    {
        return (d == a.d ? l > a.l : d > a.d);
    }
};

priority_queue<node> pq;

void add_edge (int u, int v, int w)
{
    ed[++cnt] = v;
    co[cnt] = w;
    nt[cnt] = hd[u];
    hd[u] = cnt;
}

void dijkstra()
{
    memset (dis, 0x3f, sizeof dis);
    dis[1][0] = 0;
    pq.push ({0, 0, 1});
    while (!pq.empty())
    {
        int u = pq.top().u;
        int l = pq.top().l;
        int d = pq.top().d;
        pq.pop();
        if (vis[u][l])
            continue;
        vis[u][l] = 1;
        if (u == n)
            continue;
        for (int i = hd[u]; i; i = nt[i])
        {
            int v = ed[i];
            int w = co[i] + d;
            int p = -1;
            for (int d = l; d < k; d++)
            {
                if (dis[v][d] > w)
                {
                    p = d;
                    break;
                }
            }
            if (p != -1)
            {
                for (int d = k - 1; d > p; d--)
                {
                    if (dis[v][d - 1] == 0x3f3f3f3f)
                        continue;
                    dis[v][d] = dis[v][d - 1];
                    pq.push ({dis[v][d], d, v});
                }
                dis[v][p] = w;
                pq.push ({w, p, v});
            }
        }
    }
}

int main()
{
    scanf ("%d%d%d", &k, &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf ("%d%d%d", &u, &v, &w);
        add_edge (u, v, w);
        add_edge (v, u, w);
    }
    dijkstra();
    for (int i = 0; i < k; i++)
        ans += dis[n][i];
    printf ("%d\n", ans);
    return 0;
}

洛谷 P2865 次短当成 \(k\) 短做。
洛谷 P2901 据说可以用拓扑搞。
POJ 2449 死因未知。

原文地址：http://www.cnblogs.com/cooluo/p/graph_write.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性