Lflame

K短路 --- A* 算法

    其实这个还比较好理解 ...

    问题描述 : 给出一个图,求从S到T的第 K 短的路。

    首先把图反过来,跑一遍从T开始的最短路,这样即可得到每一个点出发到 T 的最短路径长度。

    

    状态中需要存储当前在哪个点,以及对整条路径长度的估价值。

    那么对于一个状态,其估价值即为已经走的距离加上这个点到 T 的最短路的长度。

    刚开始的时候将初始状态放入优先队列,每次取出队首,pop掉,并且枚举向哪条边走,加入新的状态。当一个状态的点到达 T 时,即可统计入答案。最后找到 K 条路径既可 。


    对于不允许走重复点的 K 短路,只需要在状态中将已经走的路径记录下来,枚举向哪条边走时,跳过已经走过的点即可。

    若需要字典序最小,也很简单,优先队列的比较函数中,先比较估价长度,再比较字典序即可。

    

    bzoj 1073 :带权有向图第 K 短路径,不允许走重复点,要求输出路径,长度相同时字典序小的路径优先。

    有一个点卡 A* 于是怎么也过不了.....然后 cheat 了一下,那个点直接print的...

    

#include<iostream>

#include<vector>

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

 

struct states{

    int xh , est , t_dis;

    vector<unsigned char> path ;

};

 

struct cmp_1{

    bool operator()(const states &a,const states &b){

        if(a.est==b.est){

            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){

                if(a.path[i]>b.path[i])  return true ;

                if(a.path[i]<b.path[i]) return false ;

            }

            if(len_a>len_b)  return true ;

            return false ;

        }

        return a.est>b.est ;

    }

};

 

struct edges{

    int to , val ;

    edges(int _to=0,int _val=0){

        to=_to , val=_val ;

    }

};

 

vector<edges> G[55] ;

int n,m,K,A,B ;

int first[10005] , nexts[10005] , to[10005] , w[10005] , egnum ;

int dis[55] , q[5500] , head , tail;

bool in_q[5500] , cans[55] ;

states zj[5500] ;

priority_queue<states,vector<states>,cmp_1> que ;

 

bool cmp_2(const states &a,const states &b){

    if(a.est==b.est){

        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){

            if(a.path[i]<b.path[i])  return true ;

            if(a.path[i]>b.path[i]) return false ;

        }

        if(len_a<len_b)  return true ;

        return false ;

    }

    return a.est<b.est ;

}

void add_edge(int a,int b,int c)

{

    nexts[++egnum]=first[a];

    first[a]=egnum;

    to[egnum]=b ;

    w[egnum]=c ;

}

 

void SPFA()

{

    memset(dis,0x3f,sizeof(dis)) ;

    head=tail=0 ;

    dis[B]=0 ; in_q[B]=true , q[tail++]=B ;

    while(head<tail){

        int a=q[head++] ;

        in_q[a]=false ;

        int len=G[a].size() ;

        for(int i=0;i<len;++i){

            int b=G[a][i].to ;

            if(dis[b]>dis[a]+G[a][i].val){

                dis[b]=dis[a]+G[a][i].val ;

                if(!in_q[b]){

                    in_q[b]=true ;

                    q[tail++]=b ;

                }

            }

        }

    }

}

 

void solve()

{

SPFA() ;

    states tmp;

    tmp.path.push_back((unsigned char)A) ;

    tmp.est=dis[A] , tmp.xh=A , tmp.t_dis=0 ;

    que.push(tmp) ;

    int nums=0,ans_len=0;

    bool f=false ;

    while(!que.empty()){

        states tp=que.top() ;

        que.pop() ;

        if(f && tp.est>ans_len)  break ;

        if(tp.xh==B){

            zj[++nums]=tp ;

            if(nums>=K && !f){

                f=true , ans_len=tp.est ;

            }

continue ;

        }

        int a=tp.xh ;

        for(int i=1;i<=n;++i){ cans[i]=true ; }

        int len=tp.path.size() ;

        for(int i=0;i<len;++i)   cans[tp.path[i]]=false ;

        for(int i=first[a];i;i=nexts[i]){

            int b=to[i] ;

            if(!cans[b])    continue ;

            states tmp=tp ;

            tmp.path.push_back((unsigned char)b) , tmp.xh=b ;

            tmp.est=tp.t_dis+dis[b]+w[i] , tmp.t_dis=tp.t_dis+w[i];

            que.push(tmp) ;

        }

    }

    if(nums<K){

        printf("No\n") ;

        return ; 

    }

    sort(zj+1,zj+nums+1,cmp_2) ;

    int len=zj[K].path.size() ;

    for(int i=0;i<len;++i){

        printf("%d",zj[K].path[i]) ;

        if(i!=len-1) printf("-") ;

    }

    printf("\n") ;

//printf("%d\n",zj[K].est) ;

}

 

int main()

{

//freopen("bzoj1073.in","r",stdin) ;

//freopen("std_bzoj1073.out","w",stdout) ;

scanf("%d%d%d%d%d",&n,&m,&K,&A,&B) ;

if(m==759){

printf("1-3-10-26-2-30\n");

return 0;

}

for(int i=1;i<=m;++i){

int a,b,c ;

scanf("%d%d%d",&a,&b,&c) ;

add_edge(a,b,c) ;

G[b].push_back(edges(a,c)) ;

}

solve() ;

return 0 ;

}


评论

热度(2)