POJ 2449 Remmarguts' Date（第k短路）

Description

“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

大意

给出一个有向图，求s到t的第k短路

关于 A* 启发式搜索

给搜索一个顺序使得搜索更加合理减少无谓的搜索. 如何来确定搜索的顺序？..也就是用一个值来表示这个值为f[n]…

每次搜索取f[x]最小的拓展那么这个f[n]=h[n]+g[n]

其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) >> g(n)时，可以省略g(n),而提高效率。

A算法的估价函数可表示为： f’(n) = g’(n) + h’(n) 这里，f’(n)是估价函数，g’(n)是起点到终点的最短路径值，h’(n)是n到目标的最短路经的启发值。由于这个f’(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g’(n)，但 g(n)>=g’(n) 才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h’(n)，但h(n)<=h’(n)才可（这一点特别的重要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A算法。

原文出处 http://blog.sina.com.cn/s/blog_691ce2b701017fe3.html

Code

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100005;
const int inf = 0x3f3f3f3f;

struct node///存放“边”
{
    int from, to, w, pre;
} a[N << 1];

struct data
{   ///g 表示起点到当前点的（第x短路）距离，h表终点到当前点的（第x短路）距离
    int g, h;
    int num;///num表示当前点（的排号 or 标号）
    bool operator < (data a) const///优先队列的排序（其实也不能这么讲） 使g+h小的在队首
    {
        return a.h + a.g < h + g;
    }
};

///head[]为正向边,tail[]为逆向边（某种等效思想:有向图逆用）
///tot[i]=x;表示：此刻已经是从起点第x次到达 点i
         ///表示：此刻已经检测到从起点到点i的第x短路
int head[N], tail[N], cnt, dis[N], times[N], n, m, tot[N];
int start, over, k;
bool vis[N];

void init()
{
    cnt = 0;
    for(int i = 0; i <= n; ++i)
        dis[i] = inf, times[i] = 0, vis[i] = 0, tot[i] = 0, head[i] = -1, tail[i] = -1;
    return ;
}

void add(int from, int to, int w)
{
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].w = w;
    a[cnt].pre = head[from];
    head[from] = cnt;
    cnt++;
    a[cnt].from = to;
    a[cnt].to = from;
    a[cnt].w = w;
    a[cnt].pre = tail[to];
    tail[to] = cnt;
    cnt++;
}

void dijkstra(int over)///求终点到各点的距离
{
    dis[over] = 0;
    int now_pos = over;
    while(now_pos != -1)
    {   /// 人倒退着走 != 人在返回的路上直行
        for(int i = tail[now_pos]; ~i; i = a[i].pre)
        {
            if(vis[ a[i].to ])
                continue;
            if(dis[ a[i].to ] == inf || dis[ a[i].to ] > dis[now_pos] + a[i].w)
                dis[ a[i].to ] = dis[now_pos] + a[i].w;
        }
        vis[now_pos] = 1;

        int mmin = -1;
        now_pos = -1;
        for(int i = 0; i < n; ++i)///遍历 0 ~ n - 1 这些点
        {
            if(!vis[i] && dis[i] != inf && (dis[i] < mmin || mmin == -1 ))
            {
                mmin = dis[i];
                now_pos = i;
            }
        }
    }
    return ;
}

///启发性搜索决定了先后搜索出来的是：最短、次短、第三短...第k短
int Astar(int k)
{
    data cur, nex;
    priority_queue<data> q;

    cur.num = start;
    cur.g = 0;
    cur.h = dis[start];
    q.push(cur);

    while(q.size())
    {
        cur = q.top();
        q.pop();
        tot[ cur.num ]++;
///如果当前想拓展的点tot>k就没必要拓展了
///因为这个点已经是求到k+1短路了 从这个点继续往下搜肯定得到的是>=k+1短路的路径
        if (tot[ cur.num ] > k)
            continue;
        if (tot[over] == k)///找到第K短路 返回
            return cur.g;
        for(int i = head[cur.num]; ~i; i = a[i].pre)///链式前向星遍历
        {
            nex.num = a[i].to;
            nex.g = cur.g + a[i].w;
            nex.h = dis[ a[i].to ];
            q.push(nex);
        }
    }
    return -1;
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        init();
        int b, c, d;
        int tem = m;
        while(tem--)
        {
            scanf("%d%d%d", &b, &c, &d);
            add(b, c, d);
        }

        scanf("%d%d%d", &start, &over, &k);
        if(start == over)
            k++;
        dijkstra(over);
        cout << Astar(k) << '\n';
    }
    return 0;
}