K短路裸题。

这里的K短路是基于每个点只能访问一次,也就是说这个K短路必须是一条链。
再换句话说,这个K短路的K是有限制的,如果超过了这个限制,就输出 -1 。
这是和之前多校的次短路不一样的地方。

简单说一下K短路的解决思路:
首先我们应该认识到,最最简单的最短路算法是基于 bfs 改进而来,我们用 bfs 的思路继续拓展,在第一次到达终点后并不停止,而是继续 bfs 搜索,直到第K次到达终点,就是我们要求的答案。
当然,单纯的 bfs 是瞎 jb 搜,堆优化的spfa效率良好,但我们可以更进一步优化。
K短路于此之上还用了 A* 优化,先对反图 最短路遍历一遍,在正图遍历的时候,除了对起点 src 到当前距离 堆优化以外,还对当前距离进行答案估计,并将其优先级先于距离。

仔细想一想,其实很显然,不过为什么最短路不用 A* 优化呢?
因为有处理估值函数的时间,最短路都已经求完了。

题意:
K短路裸题。

思路:
见上。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
const int maxm = 1e5 + 5;

int idx, n, m;
int src, des;
int head[maxn], head2[maxn];
bool inq[maxn];
int dis[maxn];

struct node {
    int to, weight;
    int next;
    node(int a = 0, int b = 0, int c = 0) { to = a, weight = b, next = c; }
    bool operator<(const node& a) const { return weight > a.weight; }
} edges[maxm], redges[maxm];

struct qnode {
    int node, dist, src_dis;
    bool operator<(const qnode& a) const { return dist == a.dist ? src_dis > a.src_dis : dist > a.dist; }
} tmp;

void addEdge(int u, int v, int w)
{
    edges[idx] = node(v, w, head[u]);
    head[u] = idx;
    redges[idx] = node(u, w, head2[v]);
    head2[v] = idx++;
}

void spfa(int st)
{
    queue<int> que;
    fill(dis, dis + 1 + n, inf);
    dis[st] = 0, inq[st] = true;
    que.push(st);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        inq[u] = false;
        for (int id = head2[u]; ~id; id = redges[id].next) {
            int v = redges[id].to;
            if (dis[v] > dis[u] + redges[id].weight) {
                dis[v] = dis[u] + redges[id].weight;
                if (!inq[v]) {
                    inq[v] = true;
                    que.push(v);
                }
            }
        }
    }
}

void nthSP(int k)
{
    if (src == des)
        k++;
    priority_queue<qnode> que;
    que.push((qnode){ src, 0, 0 });
    int cnt = 0;
    while (!que.empty()) {
        tmp = que.top();
        que.pop();
        int u = tmp.node, dist = tmp.src_dis;
        if (u == des) {
            if (++cnt == k) {
                printf("%d\n", tmp.dist);
                return;
            }
        }
        for (int id = head[u]; ~id; id = edges[id].next)
            que.push((qnode){ edges[id].to, dist + edges[id].weight + dis[edges[id].to], dist + edges[id].weight });
    }
    puts("-1");
}

int main()
{
    int u, v, w, k;
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(head, -1, sizeof head), idx = 0;
        memset(head2, -1, sizeof head2);
        while (m--) {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w);
        }
        scanf("%d %d %d", &src, &des, &k);
        spfa(des);
        nthSP(k);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

最短路

HDU 1599 find the mincost route

昨天晚上从Yasola那里偷来的一道题…… 为什么Yasola这么优秀 Read more…

最短路

HDU 4725 The Shortest Path in Nya Graph

貌似是卡spfa的,但薛昊说slf优化一下也可以过 个人感觉写的非常崩 Read more…

最短路

POJ 1135 Domino Effect

这是一道多米诺骨牌的题目 从第一块骨牌出发 问最后一块倒下的骨牌在哪 Read more…