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

       原來(lái)這就是傳說(shuō)中的A*.第一次寫的A*，多多感謝alpc55推薦的這道好題。先說(shuō)說(shuō)原先讀到這到題目的想法，以前也聽(tīng)講過(guò)k短路，我還以為就是多做幾次dijkstra，或是在dijkstra算法選邊的時(shí)候控制一些條件。聽(tīng)alpc55說(shuō)是用A*啟發(fā)式搜索，直接使用廣度優(yōu)先搜索會(huì)暴空間。當(dāng)時(shí)聽(tīng)著也不怎么理解，就是把這些話記下來(lái)了。回來(lái)搞了兩天，也翻了些資料，終于把這個(gè)算法弄出來(lái)了。

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

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

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

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

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

2、放開(kāi)每個(gè)節(jié)點(diǎn)的入隊(duì)次數(shù)，求k短路，每個(gè)節(jié)點(diǎn)可以入隊(duì)k次。

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

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

如果x是s到t的第k短路徑上的一個(gè)節(jié)點(diǎn)，那么由這條路徑s到x是s到x的第m短路徑，則不可能有m>k。用反證法很容易得出：如果這條路徑是s到x的第m短路徑，如果m>k，那么經(jīng)過(guò)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