关于K短路

理解很难，但是懂了之后真的发现很简单。

主要是大家脑海里没有一个正确的运行的图。大家要想出是如何跑的就行。

前置知识：一次反向最短路（其他都算不上知识，要自己慢慢悟出来）

知识重点：反向最短路与稍后A时求的正向dis在这里的作用，A的h函数是什么

思路

dij

我们跑一次反向的最短路，有什么用将会在之后讲解。

A*

有趣的地方来了。。。
申明：dis是正向路径长，rdis是反向路径长。s是源点，t是汇点。

众所周知dis[i]+rdis[i]就是从u到v且经过i点的一条路径。（注意这里dis[i]是不停变化的，第一次求的是最短路，第二次就是u到v经过i的次短路……）

我们来想一下：
现在有一个图，从起点s开始走，发现有x个子节点。这时候我们求出s到每一个子节点的距离，这就是s到t经过x的最短路的长度。我们找出这里面最小的距离，就是s到t的最短路的长度，然后遍历这个点y。我们很容易知道，其实最短路是绝对经过点y。所以最短路在s-y-...-t中，然后进一步确定最短路在s-y-z-a-b-c-...-t中。就确定了最短路。

大家可能认为这里DFS就行了，但是其实是不行的。因为接着上述，第二短路不一定在s-y中或者最短路的其他子路径。就需要直接另找出路了。（这里如果不太懂直接在评论区评论，我会回复清楚的）

所以我们要BFS遍历，并且用priority_queue排序路径长短。一一遍历至t即可

在BFS的时候不要vis，因为如果有环的话亦可遍历环。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int s,t,k;
int head[1005];
struct e{
    int nxt,to,sum;
}edge[10005];
int rhead[1005];
e redge[10005];
int tot=0;
void add_edge(int u,int v,int w){
    tot++;
    edge[tot].nxt=head[u];
    edge[tot].to=v;
    edge[tot].sum=w;
    head[u]=tot;
    redge[tot].nxt=rhead[v];
    redge[tot].to=u;
    redge[tot].sum=w;
    rhead[v]=tot;
}
int rdis[1005];
struct node{
    int v,w;
};
struct cmp{
    bool operator () (node aa,node bb){
        return aa.w>bb.w;
    }
};
struct cmpp{
    bool operator () (node aa,node bb){
        return aa.w+rdis[aa.v]>bb.w+rdis[bb.v];
    }
};
int vis[1005];
void dij(){
    for(int i=0;i<1005;i++){
        rdis[i]=999999999;
    }
    priority_queue<node,vector<node>,cmp> q;
    node now,nxt;
    rdis[t]=0;
    now.v=t,now.w=0;
    q.push(now);
    while(!q.empty()){
        now=q.top();
        q.pop();
        if(vis[now.v])continue;
        vis[now.v]=1;
        for(int i=rhead[now.v];i;i=redge[i].nxt){
            nxt.v=redge[i].to;
            if(rdis[nxt.v]>rdis[now.v]+redge[i].sum){
                rdis[nxt.v]=rdis[now.v]+redge[i].sum;
                nxt.w=rdis[nxt.v];
                q.push(nxt);
            }
        }
    }
}
int cntt=0;
void BFS(){
    memset(vis,0,sizeof(vis));
    priority_queue<node,vector<node>,cmpp> q;
    node now,nxt;
    now.v=s,now.w=0;
    q.push(now);
    vis[s]--;
    if(s==t)cntt--;
    while(!q.empty()){
        now=q.top();
        q.pop();
        if(vis[now.v]>=k)continue;
        vis[now.v]++;
        if(now.v==t){
            cntt++;
        }
        if(cntt==k){
            printf("%d\n",now.w);
            return ;
        }
        for(int i=head[now.v];i;i=edge[i].nxt){
            nxt.v=edge[i].to;
            nxt.w=now.w+edge[i].sum;
            q.push(nxt);
        }
    }
    printf("-1\n");
    return ;
}
int main(){
    int a,b,l;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&l);
        add_edge(a,b,l);
    }
    scanf("%d%d%d",&s,&t,&k);
    dij();
    BFS();
    return 0;
}

本文链接：http://kaispace.com.cn/index.php/archives/651/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者