Remmarguts' Date

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

Source

POJ Monthly,Zeyuan Zhu

       原来这就是传说中的A*.第一次写的A*，多多感谢alpc55推荐的这道好题。先说说原先读到这到题目的想法，以前也听讲过k短路，我还以为就是多做几次dijkstra，或是在dijkstra算法选边的时候控制一些条件。听alpc55说是用A*启发式搜索，直接使用广度优先搜索会暴空间。当时听着也不怎么理解，就是把这些话记下来了。回来搞了两天，也翻了些资料，终于把这个算法弄出来了。

       先说说启发式搜索吧。通常在解决问题的时候，我们需要用到搜索算法，由已知状态推出新的状态，然后检验新的状态是不是就是我们要求的最优解。检验完所有的状态实际上就相当于遍历了一张隐式图。遗憾的是，所有的状态组成的状态空间往往是成指数级别增长的，也就造成了遍历需要用到指数级别的时间，因此，纯粹的暴力搜索，时空效率都比较低。当然，我们在生活中遇到了类似于搜索的问题，我们并不会盲目地去搜寻每一种状态，我们会通过我们的思维，选择一条最接近于目标的路径或者是近似于最短的路径去完成搜索任务。当我们想要计算机去完成这样一项搜索任务的时候，就得让计算机像人一样能够区分尽量短的路径，以便高效地找到最优解。这时可以把计算机看作是一种智能体(agent)可以实现由初始状态向目标状态的转移。

       有一种贪心策略，即每一步转移都由计算机选择当前的最优解生成新的状态，一直到达目标状态为止。这样做的时间效率虽然较高，但是贪心的策略只是用到了局部的最优解，并不能保证最后到达目标状态得到的是全局最优解。在能保证全局最优解的范围内，贪心算法还是很有用的。比如说我们熟知的Dijkstra算法求单源最短路。每次选择距离源节点最短距离的待扩展节点进行扩展，最后就能生成源节点到所有节点的最短路径。下面会讲到Dijkstra的扩展，当理解了这个算法之后，我想，你会对Dijkstra有更深入的理解。

       这就是A*算法。定义初始状态S，目标状态t，g(s)是由初始状态转移到当前状态s所经过的路径长度，h*(s)是当前状态s距离目标状态t的实际长度，但是一般情况下我们是不知道h*(s)的值的，所以还要定义一个估价函数h(s)，是对h*(s)函数值的下界的估计，也就是有h(s)<=h*(s)，这样需要一个条件，使得由s1生成的每状态s2，都有h(s1)<=h(s2)，这是一个相容的估价函数。再定义f(s)=g(s)+h(s)为启发函数，因为h(s)是单调递增的，所以f(s)也是单调递增的。这样f(s)就估计出了由初始状态的总体代价。A*算法就通过构造这样一个启发函数，将所有的待扩展状态加入到队列里，每次从队列里选择f(s)值最小的状态进行扩展。由于启发函数的作用，使得计算机在进行状态转移的时候尽量避开了不可能产生最优解的分支，而选择相对较接近最优解的路径进行搜索，提高了搜索效率。

       讲到这里，可能已经对A*算法的概念有点眉目了。下面我再来做一个比较，就用上面讲到的Dijkstra的例子。Dijkstra算法说的是每次选择距离源点最短距离的点进行扩展。当然可以看做事先将源点到所有节点距离的值保存在一个优先队列里，每次从优先队列里出队最短距离的点扩展，每个点的扩展涉及到要更新队列里所有待扩展节点的距离值，每个节点只能进队一次，就需要有一个表来记录每个节点的入队次数（就是算法中用到的标记数组）。将Dijkstra求最短路的方法扩展，这道题目要求的是两点间第k短路。类比于Dijkstra算法可以首先确定下面几个搜索策略：

1、用优先队列保存节点进行搜索。

2、放开每个节点的入队次数，求k短路，每个节点可以入队k次。

首先看第一个策略，在A*算法中用优先队列就是要用到启发函数f(s)确定状态在优先队列里面的优先级。其实Dijkstra用到的优先队列实际上就是估价函数值为0，启发函数f(s)=g(s)，即是选取到源点距离最近的点进行扩展。因为h(s)=0满足了估价函数相容这个条件。这题求k短路就不能单纯的使用h(s)=0这个估价函数。解决这道题的时候选取h(x)=dt(x), dt(x)是x节点到目标节点的最短距离。最短距离可以开始由Dijkstra直接求得。

再看第二个策略，控制每个节点的入队（或出队）次数为k次，可以找到第k短路径。可能这样想有点主观的套用，那么我就先来证明这样一个结论：

如果x是s到t的第k短路径上的一个节点，那么由这条路径s到x是s到x的第m短路径，则不可能有m>k。用反证法很容易得出：如果这条路径是s到x的第m短路径，如果m>k，那么经过x到t的路径就有m-1条比当前路径要短，不符合当前路径是s到t的第k短路径。

  1#include <stdio.h>
  2#include <string.h>
  3#include <vector>
  4using namespace std;
  5
  6const int INF=1234567890;
  7struct P
  8{
  9    int x,len;
 10}heap[1000005];
 11int size,n,m,dist[1005],s,t,ti,out[1005];
 12vector<struct P> g[1005],r[1005]; //有重边的情况
 13
 14void Insert(int v);
 15struct P Del();
 16void dijkstra();
 17int Astar();
 18
 19int main()
 20{
 21    int i,a,b,L;
 22    struct P temp;
 23//    freopen("2449.txt","r",stdin);
 24    scanf("%d%d",&n,&m);
 25    for(i=0; i<m; i++)
 26    {
 27        scanf("%d%d%d",&a,&b,&L);
 28        temp.len=L;
 29        temp.x=b;
 30        g[a].push_back(temp);
 31        temp.len=L;
 32        temp.x=a;
 33        r[b].push_back(temp);
 34    }
 35    scanf("%d%d%d",&s,&t,&ti);
 36    if(s == t) ti++;
 37    printf("%d\n",Astar());
 38    return 0;
 39}
 40void dijkstra()
 41{
 42    int i,u,min;
 43    bool mark[1005]={false};
 44    vector<struct P>::iterator iter;
 45    for(i=1; i<=n; i++)
 46        dist[i]=INF;
 47    dist[t]=0;
 48    while(1)
 49    {
 50        u=-1;
 51        min=INF;
 52        for(i=1; i<=n; i++)
 53        {
 54            if(!mark[i] && dist[i] < min)
 55            {
 56                min=dist[i];
 57                u=i;
 58            }
 59        }
 60        if(u == -1) break;
 61        mark[u]=true;
 62        for(iter=r[u].begin(); iter!=r[u].end(); iter++)
 63        {
 64            if(!mark[(*iter).x] && dist[(*iter).x] > dist[u]+(*iter).len)
 65                dist[(*iter).x]=dist[u]+(*iter).len;
 66        }
 67    }
 68}
 69void Insert(struct P v)
 70{
 71    int i;
 72    heap[size++]=v;
 73    i=size-1;
 74    while(i > 0)
 75    {
 76        if(v.len < heap[(i-1)/2].len)
 77        {
 78            heap[i]=heap[(i-1)/2];
 79            i=(i-1)/2;
 80        }
 81        else
 82            break;
 83    }
 84    heap[i]=v;
 85}
 86struct P Del()
 87{
 88    struct P r,temp;
 89    int i=0,ic;
 90    r=heap[0];
 91    heap[0]=heap[--size];
 92    temp=heap[0];
 93    while(2*i+1 < size)
 94    {
 95        ic=2*i+1;
 96        while(ic+1 < size && heap[ic+1].len < heap[ic].len)
 97            ic++;
 98        if(heap[ic].len < temp.len)
 99        {
100            heap[i]=heap[ic];
101            i=ic;
102        }
103        else break;
104    }
105    heap[i]=temp;
106    return r;
107}
108int Astar()
109{
110    int ds;
111    struct P v,temp;
112    vector<struct P>::iterator iter;
113    size=0;
114    dijkstra();
115    v.x=s;
116    v.len=dist[s];
117    Insert(v);
118    memset(out,0,sizeof(out));
119    while(size > 0 && out[t] < ti)
120    {
121        v=Del();
122        if(out[v.x] >= ti)
123            continue;
124        out[v.x]++;
125        if(v.x == t && out[v.x] == ti)
126        {
127            return v.len;
128        }
129        for(iter=g[v.x].begin(); iter!=g[v.x].end(); iter++)
130        {
131            if(out[(*iter).x] >= ti)
132                continue;
133            ds=v.len-dist[v.x];
134            temp.len=ds+(*iter).len+dist[(*iter).x];
135            temp.x=(*iter).x;
136            Insert(temp);
137        }
138    }
139    return -1;
140}
141
142