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