问题描述

说的简单点就是给你一张n个点m条边的有向图和起点S,终点T。求从S出发到T的第K短路。

输入

第一行n,m。
接下来m行,每行描述一条有向边。
最后一行S,T,K三个数

输出

输出第K短路的长度,如果不存在则输出-1。

思路

这就是K短路的模板题吧。用可持久化左偏树维护自然是不会的。

首先可以考虑用优先队列搜索,类似于上一篇博客中的方法。显然这样的时间复杂度是不符合要求的,于是可以用启发式搜索进行优化。

A* 中的估价函数也不难设计,为了确保正确性,估价函数值应该要比真实值要小,于是估价函数可以设计为从该点到T的最短路。

细节

  1. 如果S==T,要K++。 太毒瘤啦
  2. 要注意K短路不存在的情况

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f
#define MAXN 1005
#define MAXE 100005
using namespace std;

struct Node
{
    int x, dis1, dis2; //dis1实际走过距离,dis2估计总距离
    Node(int a, int b, int c)
    {
        x=a; dis1=b; dis2=c;
    }
    friend bool operator < (Node x, Node y)
    {
        return x.dis2>y.dis2; //小根堆 
    }
};

int n, m, a, b, t, dis[MAXN], S, T, K, ans=INF;
bool vis[MAXN];

struct Graph
{
    int cnt, head[MAXN];
    struct Edge {int next, to, dis;} edge[MAXE];

    void addedge(int from, int to, int dis)
    {
        edge[++cnt].next=head[from];
        edge[cnt].to=to;
        edge[cnt].dis=dis;
        head[from]=cnt;
    }

    void spfa()
    {
        memset(dis, 0x3f, sizeof(dis));
        queue<int> q;
        dis[T]=0; vis[T]=true;
        q.push(T);
        while(!q.empty())
        {
            int x=q.front(); q.pop();
            vis[x]=false;
            for(int i=head[x]; i; i=edge[i].next)
            {
                int to=edge[i].to;
                if(dis[to]<dis[x]+edge[i].dis) continue;
                dis[to]=dis[x]+edge[i].dis;
                if(!vis[to]) q.push(to), vis[to]=true;
            }
        } 
    }

    void Astar()
    {
        int tot=0;
        priority_queue<Node> q;

        if(S==T) K++; //注意!!! 
        q.push(Node(S, 0, dis[S]));
        while(!q.empty())
        {
            Node top=q.top(); q.pop();
            if(top.x==T)
            {
                tot++;
                if(tot==K) {ans=top.dis1; return;}
            }
            for(int i=head[top.x]; i; i=edge[i].next)
            {
                int dis1=top.dis1+edge[i].dis;
                int dis2=dis1+dis[edge[i].to];
                q.push(Node(edge[i].to, dis1, dis2));
            }
        }
    }

} G1, G2;

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &a, &b, &t);
        G1.addedge(a, b, t);
        G2.addedge(b, a, t);
    }
    scanf("%d%d%d", &S, &T, &K);
    G2.spfa();
    G1.Astar();
    if(ans==INF) printf("-1\n"); //K短路可能不存在 
    else printf("%d\n", ans);
}

发表评论

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