浅谈K短路
关于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/
如果未注明出处,复制公开后需将注明本博客链接。打赏作者
未完待续是什么鬼啊qwq 我正准备看看K短路怎么写然后就看到了未完待续???
来了来了QAQ
大哥,真正能保证复杂度的K短路是要用可持久化左偏树来维护的……