Menu
Article Graph

POJ 2449 Remmarguts' Date

NodeKey

NodeKey

• 3 min read

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;
}
Share