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*啟發(fā)式搜索，直接使用廣度優(yōu)先搜索會暴空間。當(dāng)時聽著也不怎么理解，就是把這些話記下來了。回來搞了兩天，也翻了些資料，終于把這個算法弄出來了。

       先說說啟發(fā)式搜索吧。通常在解決問題的時候，我們需要用到搜索算法，由已知狀態(tài)推出新的狀態(tài)，然后檢驗新的狀態(tài)是不是就是我們要求的最優(yōu)解。檢驗完所有的狀態(tài)實際上就相當(dāng)于遍歷了一張隱式圖。遺憾的是，所有的狀態(tài)組成的狀態(tài)空間往往是成指數(shù)級別增長的，也就造成了遍歷需要用到指數(shù)級別的時間，因此，純粹的暴力搜索，時空效率都比較低。當(dāng)然，我們在生活中遇到了類似于搜索的問題，我們并不會盲目地去搜尋每一種狀態(tài)，我們會通過我們的思維，選擇一條最接近于目標(biāo)的路徑或者是近似于最短的路徑去完成搜索任務(wù)。當(dāng)我們想要計算機(jī)去完成這樣一項搜索任務(wù)的時候，就得讓計算機(jī)像人一樣能夠區(qū)分盡量短的路徑，以便高效地找到最優(yōu)解。這時可以把計算機(jī)看作是一種智能體(agent)可以實現(xiàn)由初始狀態(tài)向目標(biāo)狀態(tài)的轉(zhuǎn)移。

       有一種貪心策略，即每一步轉(zhuǎn)移都由計算機(jī)選擇當(dāng)前的最優(yōu)解生成新的狀態(tài)，一直到達(dá)目標(biāo)狀態(tài)為止。這樣做的時間效率雖然較高，但是貪心的策略只是用到了局部的最優(yōu)解，并不能保證最后到達(dá)目標(biāo)狀態(tài)得到的是全局最優(yōu)解。在能保證全局最優(yōu)解的范圍內(nèi)，貪心算法還是很有用的。比如說我們熟知的Dijkstra算法求單源最短路。每次選擇距離源節(jié)點最短距離的待擴(kuò)展節(jié)點進(jìn)行擴(kuò)展，最后就能生成源節(jié)點到所有節(jié)點的最短路徑。下面會講到Dijkstra的擴(kuò)展，當(dāng)理解了這個算法之后，我想，你會對Dijkstra有更深入的理解。

       這就是A*算法。定義初始狀態(tài)S，目標(biāo)狀態(tài)t，g(s)是由初始狀態(tài)轉(zhuǎn)移到當(dāng)前狀態(tài)s所經(jīng)過的路徑長度，h*(s)是當(dāng)前狀態(tài)s距離目標(biāo)狀態(tài)t的實際長度，但是一般情況下我們是不知道h*(s)的值的，所以還要定義一個估價函數(shù)h(s)，是對h*(s)函數(shù)值的下界的估計，也就是有h(s)<=h*(s)，這樣需要一個條件，使得由s1生成的每狀態(tài)s2，都有h(s1)<=h(s2)，這是一個相容的估價函數(shù)。再定義f(s)=g(s)+h(s)為啟發(fā)函數(shù)，因為h(s)是單調(diào)遞增的，所以f(s)也是單調(diào)遞增的。這樣f(s)就估計出了由初始狀態(tài)的總體代價。A*算法就通過構(gòu)造這樣一個啟發(fā)函數(shù)，將所有的待擴(kuò)展?fàn)顟B(tài)加入到隊列里，每次從隊列里選擇f(s)值最小的狀態(tài)進(jìn)行擴(kuò)展。由于啟發(fā)函數(shù)的作用，使得計算機(jī)在進(jìn)行狀態(tài)轉(zhuǎn)移的時候盡量避開了不可能產(chǎn)生最優(yōu)解的分支，而選擇相對較接近最優(yōu)解的路徑進(jìn)行搜索，提高了搜索效率。

       講到這里，可能已經(jīng)對A*算法的概念有點眉目了。下面我再來做一個比較，就用上面講到的Dijkstra的例子。Dijkstra算法說的是每次選擇距離源點最短距離的點進(jìn)行擴(kuò)展。當(dāng)然可以看做事先將源點到所有節(jié)點距離的值保存在一個優(yōu)先隊列里，每次從優(yōu)先隊列里出隊最短距離的點擴(kuò)展，每個點的擴(kuò)展涉及到要更新隊列里所有待擴(kuò)展節(jié)點的距離值，每個節(jié)點只能進(jìn)隊一次，就需要有一個表來記錄每個節(jié)點的入隊次數(shù)（就是算法中用到的標(biāo)記數(shù)組）。將Dijkstra求最短路的方法擴(kuò)展，這道題目要求的是兩點間第k短路。類比于Dijkstra算法可以首先確定下面幾個搜索策略：

1、用優(yōu)先隊列保存節(jié)點進(jìn)行搜索。

2、放開每個節(jié)點的入隊次數(shù)，求k短路，每個節(jié)點可以入隊k次。

首先看第一個策略，在A*算法中用優(yōu)先隊列就是要用到啟發(fā)函數(shù)f(s)確定狀態(tài)在優(yōu)先隊列里面的優(yōu)先級。其實Dijkstra用到的優(yōu)先隊列實際上就是估價函數(shù)值為0，啟發(fā)函數(shù)f(s)=g(s)，即是選取到源點距離最近的點進(jìn)行擴(kuò)展。因為h(s)=0滿足了估價函數(shù)相容這個條件。這題求k短路就不能單純的使用h(s)=0這個估價函數(shù)。解決這道題的時候選取h(x)=dt(x), dt(x)是x節(jié)點到目標(biāo)節(jié)點的最短距離。最短距離可以開始由Dijkstra直接求得。

再看第二個策略，控制每個節(jié)點的入隊（或出隊）次數(shù)為k次，可以找到第k短路徑。可能這樣想有點主觀的套用，那么我就先來證明這樣一個結(jié)論：

如果x是s到t的第k短路徑上的一個節(jié)點，那么由這條路徑s到x是s到x的第m短路徑，則不可能有m>k。用反證法很容易得出：如果這條路徑是s到x的第m短路徑，如果m>k，那么經(jīng)過x到t的路徑就有m-1條比當(dāng)前路徑要短，不符合當(dāng)前路徑是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