K短路 --- Yen 算法
资料：
https://ycool.com/post/krb8pah
https://ycool.com/post/ppswum7 这两篇都讲得很详细，是同一个人写的
这是一个很强大的算法，其本质也是属于 A* 的。%%%听说有用可持久化堆来做 K 短路的可以做到 O(nlogn + mlogm + klogk)，不过Yen算法在很多情况下还是够用了... (Orzzz 可是蒟蒻的我依然看了好久才看懂)
Yen 算法是一种偏离算法，相当于每次在原有路径上，通过偏离，找到在原有路径的基础上次长的路径。
状态中存储了偏离点dev，即这条路径被之前某条路径偏离得到时，不属于之前那条路径的第一个点。状态还存储了哪些边在之前偏离时被禁止了的。
算法的开始，先求一遍 S 到 T 的最短路，作为初始状态的路径，为了契合定义，这个状态的dev为最短路径上第二个点，然后将其放入优先队列。每次从队首取出一个状态 sta，pop掉，然后在这个状态的路径上，从dev之前的一个点开始一直到 T 点(可以走重复点时，否则为T点之前的那个点)这些点中选取一个点 a，找到从点 a 出发通过其他边到达 T 点的最短路径。这时得到一个新的状态 sta'，假设走了边 (a , b)，则其 dev 为 b，并且要将边(a , b)放入这个状态的禁止边的vector中，并且若sta' 与 sta都是从同一个点偏离得到，那么需要将sta'的禁止边的vector拷贝入sta，最后将sta'放入优先队列。
其中怎么找从点 a 出发通过其他边(即不是sta的禁止边的边)到达 T 点的最短路径呢 ？ 如果题目允许走重复的点，那么直接预先处理出每个点到 T 的最短距离，找的时候for一遍点 a 的边，找到 w(a,b) + dis[b] 最小的点 b 即可。如果题目不允许走重复的点，那么我们将 sta 中 a 之前的点全部ban掉，再跑一遍最短路就可以了。
bzoj1073这道题，是需要字典序最小的，那怎么办呢 ？
我们将整个图的边反过来，可以发现每一条原来的 S-T路径都对应一条现在的 T-S 的路径，并且路径长度不变。然后做最短路时，存储一个 pre ，表示这个点的 dis 从哪个点更新过来，那么当dis[v] == dis[u] + w(u,v)时，判断 u 的字典序是否小于 pre[v]，小于则更新pre[v]=u。 这样就保证每个点的前一个点的字典序尽量小，对应到反图之前的路径，就是每个点的后一个点的字典序尽量小，正好符合字典序最小的定义。
代码 ：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct states
{
vector<int> ban ; //偏离点的前一个点的边限制
vector<int> path ; //存边
int dev ; //表示偏离点的出边在path中的序号
int t_len ;
};
struct Dijk_states
{
int xh , t_dis ;
Dijk_states(int _xh=0,int _t_dis=0){
xh=_xh , t_dis=_t_dis ;
}
};
priority_queue<Dijk_states> Dijk_que ;
priority_queue<states> que ;
int n,m,K,A,B ;
int first[10005],nexts[10005],to[10005],w[10005],from[10005],egnum ;
int dis[55] , pre[55] , INF , pre_eg[55];
int ban_eg[10005] , TTT , ban_p[55];
bool over[55] ;
//ban_p 是防止转移进来 over 是防止转移出去
bool operator<(const Dijk_states &a,const Dijk_states &b)
{
return a.t_dis>b.t_dis ;
}
bool operator<(const states &a,const states &b)
{
if(a.t_len==b.t_len){
int len_a=a.path.size() , len_b=b.path.size() ;
int t=min(len_a,len_b) ;
for(int i=1;i<=t;++i){
int ta=from[a.path[len_a-i]] , tb=from[b.path[len_b-i]];
if(ta>tb) return true ;
if(ta<tb) return false ;
}
return len_a>len_b ;
}
return a.t_len>b.t_len ;
}
void add_edge(int a,int b,int c)
{
nexts[++egnum]=first[a] ;
first[a]=egnum ;
to[egnum]=b ;
from[egnum]=a ;
w[egnum]=c ;
}
void Dijkstra() //信息要在函数外先初始化
{
while(!Dijk_que.empty()){
Dijk_states tp=Dijk_que.top() ;
Dijk_que.pop() ;
if(over[tp.xh]) continue ;
over[tp.xh]=true ;
int a=tp.xh ;
for(int i=first[a];i;i=nexts[i]){
if(ban_eg[i]==TTT) continue ;
int b=to[i] ;
if(ban_p[b]==TTT) continue ;
if(dis[b]==dis[a]+w[i] && pre[b]>a){
pre[b]=a , pre_eg[b]=i ;
}
if(dis[b]>dis[a]+w[i]){
dis[b]=dis[a]+w[i] ;
pre[b]=a , pre_eg[b]=i ;
Dijk_que.push(Dijk_states(b,dis[b])) ;
}
}
}
}
void rev(states &a)
{
reverse(a.path.begin(),a.path.end()) ;
}
void ext(const states &tp)
{
int len=tp.path.size() ;
for(int i=tp.dev-1;i<len;++i){
++ TTT ;
while(!Dijk_que.empty()){
Dijk_que.pop() ;
}
if(i==tp.dev-1){
int l=tp.ban.size() ;
for(int j=0;j<l;++j) ban_eg[tp.ban[j]]=TTT ;
}
ban_eg[tp.path[i]]=TTT ;
memset(dis,0x3f,sizeof(dis)) ;
memset(over,false,sizeof(over)) ;
dis[B]=0 ;
for(int j=0;j<=i;++j){
ban_p[from[tp.path[j]]]=TTT ;
if(j!=i) over[from[tp.path[j]]]=true ;
int a=from[tp.path[j]] ;
if(j){
dis[a]=dis[from[tp.path[j-1]]]+w[tp.path[j-1]] ;
pre_eg[a]=tp.path[j-1] , pre[a]=from[tp.path[j-1]];
}
if(j==i) Dijk_que.push(Dijk_states(a,dis[a])) ;
}
Dijkstra() ;
if(dis[A]==INF) continue ;
int t=A;
states tmp ;
while(t!=B){
tmp.path.push_back(pre_eg[t]) ;
t=pre[t] ;
}
rev(tmp) ; tmp.dev=i+1 ;
if(i==tp.dev-1) tmp.ban=tp.ban ;
else tmp.ban.push_back(tp.path[i]) ;
tmp.ban.push_back(tmp.path[i]) , tmp.t_len=dis[A] ;
que.push(tmp) ;
}
//可优化
}
void ss(){
cout << que.size() << '\n';
}
void print()
{
cout << que.top().t_len << '\n' ;
int len=que.top().path.size() ;
for(int i=0;i<len;++i){
cout << from[que.top().path[i]] << ' ' ;
}
cout << A ;
cout << '\n' ;
}
void solve()
{
memset(dis,0x3f,sizeof(dis)) ;
memset(over,false,sizeof(over)) ;
++TTT ;
INF=dis[0] ;
dis[B]=0 , Dijk_que.push(Dijk_states(B,dis[B])) ;
Dijkstra() ;
states tmp ;
if(dis[A]==INF){
printf("No\n") ;
return ;
}
int t=A ;
while(t!=B){
tmp.path.push_back(pre_eg[t]) ;
t=pre[t] ;
};
rev(tmp) ; tmp.dev=1 , tmp.ban.push_back(tmp.path[0]) ;
tmp.t_len=dis[A] ;
que.push(tmp) ;
int nums=0 ;
while(!que.empty()){
nums ++ ;
if(nums==K) break ;
states tp=que.top() ;
que.pop() ;
ext(tp) ;
}
if(nums<K){
printf("No\n") ;
return ;
}
states tp=que.top() ;
int len=tp.path.size() ;
printf("%d-",A) ;
for(int i=len-1;i>=0;--i){
printf("%d",from[tp.path[i]]) ;
if(i!=0) printf("-") ;
}
printf("\n") ;
//printf("%d\n",tp.t_len) ;
}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&K,&A,&B) ;
for(int i=1;i<=m;++i){
int a,b,c;
scanf("%d%d%d",&a,&b,&c) ;
add_edge(b,a,c) ;
}
solve() ;
return 0 ;
}
评论