A*、第 k 短路

description

"Good man never makes girls wait or breaks an appointment!" said the mandarin duck father. Softly touching his little ducks' head, he told them a story.

"Prince Remmarguts lives in his kingdom UDF – United Delta of Freedom. One day their neighboring country sent them Princess Uyuw on a diplomatic mission."

"Erenow, the princess sent Remmarguts a letter, informing him that she would come to the hall and hold commercial talks with UDF if and only if the prince go and meet her via the K-th shortest path. (in fact, Uyuw does not want to come at all)"

Being interested in the trade development and such a lovely girl, Prince Remmarguts really became enamored. He needs you - the prime minister's help!

DETAILS: UDF's capital consists of N stations. The hall is numbered S, while the station numbered T denotes prince' current place. M muddy directed sideways connect some of the stations. Remmarguts' path to welcome the princess might include the same station twice or more than twice, even it is the station with number S or T. Different paths with same length will be considered disparate.

Input

The first line contains two integer numbers N and M (1 <= N <= 1000, 0 <= M <= 100000). Stations are numbered from 1 to N. Each of the following M lines contains three integer numbers A, B and T (1 <= A, B <= N, 1 <= T <= 100). It shows that there is a directed sideway from A-th station to B-th station with time T.

The last line consists of three integer numbers S, T and K (1 <= S, T <= N, 1 <= K <= 1000).

Output

A single line consisting of a single integer number: the length (time required) to welcome Princess Uyuw using the K-th shortest path. If K-th shortest path does not exist, you should output "-1" (without quotes) instead.

Sample Input

2 2
1 2 5
2 1 4
1 2 2

Sample Output

14

题解

A*算法:

为启发式算法中很重要的一种,被广泛应用在最优路径求解和一些策略设计的问题中。而A算法最为核心的部分,就在于它的一个估值函数的设计上:
f(n)=g(n)+h(n)f(n)=g(n)+h(n)
其中f(n)f(n)是每个可能试探点的估值,它有两部分组成:一部分为g(n)g(n),它表示从起始搜索点到当前点的代价(通常用某结点在搜索树中的深度来表示)。另一部分,即h(n)h(n),它表示启发式搜索中最为重要的一部分,即当前结点到目标结点的估值,h(n)h(n)设计的好坏,直接影响着具有此种启发式函数的启发式算法的是否能称为A
算法。

一种具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是:

  1. 搜索树上存在着从起始点到终了点的最优路径。
  2. 问题域是有限的。
  3. 所有结点的子结点的搜索代价值>0。
  4. h(n) <= h * (n) (h*(n)为实际问题的代价值)。

一般的搜索前三条都可以满足,而第四点就要视情况而定了。

第K路

K短路的定义:假设从1出发,有M条长度不同的路径可以到达点N,则K短路就是这M条路径中第K小的路径长度。
以上所述,设f[n]为最终所求,则f(n)=g(n)+h(n);h(n)就是我们所说的‘启发式函数’,表示为
重点t到其余一点p的路径长度
,g(n)表示g当前从s到p所走的路径的长度。

估价函数=当前值+当前位置到终点的距离

解决思路:

  1. 将有向图的所有边反向,以原终点t为源点,求解t到所有点的最短距离;
  2. 新建一个优先队列,将源点s加入到队列中;
  3. 从优先级队列中弹出f(p)最小的点p,如果点p就是t,则计算t出队的次数;

如果当前为t的第k次出队,则当前路径的长度就是s到t的第k短路的长度,算法结束;
否则遍历与p相连的所有的边,将扩展出的到p的邻接点信息加入到优先级队列;

代码

#include<string.h>
#include<algorithm>
#include<queue> 
using namespace std;
#define INF 0xffffff
#define MAXN 100010
struct node
{
    int to;
    int val;
    int next;
};
struct node2
{
    int to;
    int g,f;
    bool operator<(const node2 &r ) const  
    {  
        if(r.f==f)  
            return r.g<g;  
        return r.f<f;  
    }   
};
node edge[MAXN],edge2[MAXN];
int n,m,s,t,k,cnt,cnt2,ans;
int dis[1010],visit[1010],head[1010],head2[1010];
void init()
{
    memset(head,-1,sizeof(head));
    memset(head2,-1,sizeof(head2));
    cnt=cnt2=1;
}
void addedge(int from,int to,int val)
{
    edge[cnt].to=to;
    edge[cnt].val=val;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}
void addedge2(int from,int to,int val)
{
    edge2[cnt2].to=to;
    edge2[cnt2].val=val;
    edge2[cnt2].next=head2[from];
    head2[from]=cnt2++;
}
bool spfa(int s,int n,int head[],node edge[],int dist[])  
{  
    queue<int>Q1;  
    int inq[1010];  
    for(int i=0;i<=n;i++)  
    {  
        dis[i]=INF;  
        inq[i]=0;  
    }  
    dis[s]=0;  
    Q1.push(s);  
    inq[s]++;  
    while(!Q1.empty())  
    {  
        int q=Q1.front();  
        Q1.pop();  
        inq[q]--;  
        if(inq[q]>n)
            return false;  
        int k=head[q];  
        while(k>=0)  
        {  
            if(dist[edge[k].to]>dist[q]+edge[k].val)  
            {  
                dist[edge[k].to]=edge[k].val+dist[q];  
                if(!inq[edge[k].to])  
                {  
                    inq[edge[k].to]++;  
                    Q1.push(edge[k].to);  
                }  
            }  
            k=edge[k].next;  
        }  
    }  
    return true;  
}
int A_star(int s,int t,int n,int k,int head[],node edge[],int dist[]) 
{  
    node2 e,ne;  
    int cnt=0;  
    priority_queue<node2>Q;  
    if(s==t)
        k++;  
    if(dis[s]==INF)  
        return -1;  
    e.to=s;  
    e.g=0;  
    e.f=e.g+dis[e.to];  
    Q.push(e);  

    while(!Q.empty())  
    {  
        e=Q.top();  
        Q.pop();  
        if(e.to==t)//找到一条最短路径  
        {  
            cnt++;  
        }  
        if(cnt==k)//找到k短路  
        {  
            return e.g;  
        }  
        for(int i=head[e.to]; i!=-1; i=edge[i].next)  
        {  
            ne.to=edge[i].to;  
            ne.g=e.g+edge[i].val;  
            ne.f=ne.g+dis[ne.to];  
            Q.push(ne);  
        }  
    }  
    return -1;  
}  
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c);
            addedge2(b,a,c);
        }
        scanf("%d%d%d",&s,&t,&k);
        spfa(t,n,head2,edge2,dis);
        ans=A_star(s,t,n,k,head,edge,dis);
        printf("%d\n",ans);
    }

    return 0;
}