称号：poj 2449 Remmarguts' Date

意甲冠军：给定一个图，乞讨k短路。

算法：SPFA求最短路 + AStar

以下引用大牛的分析：

首先，为了说话方便，列出一些术语：

在启示式搜索中，对于每一个状态 x。启示函数 f(x) 一般是这种形式：

f(x) = g(x) + h(x)

当中 g(x) 是从初始状态走到 x 所花的代价；h(x)
是从 x 走到目标状态所须要的代价的预计值。

相对于 h(x)。另一个概念叫 h*(x)，表示从 x 走到目标状态所须要的实际最小代价（当然，这个值有时我们是事先无法知道的）。

假设在你的启示函数里，能保证 h(x) <= h*(x)。也就是说，你不能高估了从 x 走到目标状态所须要的代价，那就能够说这个搜索是 A* 算法（这里的“*”，英文就读作 star）。

A* 算法的特点是，假设存在从初始状态走到目标状态的最小代价的解。那么用 A* 算法搜索时，第一个找到的解就一定是最小代价的。这就是所谓的可採纳（admissible）。

1. 求前 K 短的 能够带环的 路径（的长度）

1.1. 典型的启示式搜索

设起点为 s；终点为 t。对于一个点 v，dt(v) 表示从 v 走到 t 的最短路径的长度（能够在初始化的时候全都算好）。

能够用最典型的启示式搜索来解这个问题。

一个状态 x 表示的是从 s 走到某个点的一条路径。把这个点记作 x.v，把这条路径的长度记作 x.len。接着。我们能够使用下面启示函数：

g(x) = x.len;  h(x) = dt(x.v); ∴ f(x) = g(x) + h(x) = x.len + dt(x.v)

初始状态中。 x.v = s； x.len
= 0。

然后每次让优先队列（所谓的 Open
表）中 f(x) 值最小的状态 x
出队，再跟据图中全部从 x.v 出发的边发展下一层状态，让它们进队列。优先队列中不存在判反复的问题，由于每一个状态所代表的路径肯定是不一样的。

不难想通，这是一个 A* 算法。由于这里的 h(x) 本身就是 h*(x)，当然满足 h(x) <= h*(x)。

因此能够说，在每次出队列的状态 x 中，第一次遇到 x.v == t 时。就找到了从 s 到 t 的第一短的路径，它的长度就是 f(x)……第 k 次遇到 x.v == t 时，就找到了从 s 到 t 的第 k 短的路径。

这就是传说中的启示式搜索，由于有启示函数，并且可以利用广搜的特性，不断的扩展。

感觉是一个非常经典的题目。

注意的是，假如起点和终点是同一点，由于第一次走到的就是，所以必须K++

继续膜拜大牛，上我写的挫代码：

#include <cstdio>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

const int N = 1200;

const int inf = 0x3f3f3f3f;

struct Node

{

    int to,val;

};

vector<Node> g[N],rg[N];

int dis[N];

bool vis[N];

int n,m;

void SPFA(int src)

{

    int i;

    memset(dis,inf,sizeof(dis));

    dis[src] = 0;

    queue<int> Q;

    Q.push(src);

    while(!Q.empty())

    {

        int u,v;

        u = Q.front();

        Q.pop();

        for(int i = 0;i<g[u].size();i++)

        {

            v = g[u][i].to;

            if(dis[v]>dis[u]+g[u][i].val) //记得这里这样写  最后改一下vis

            {

                dis[v] = dis[u] + g[u][i].val;

                Q.push(v);

            }

        }

    }

}

struct Tree

{

    int v,len,h;

    bool operator < (const Tree & a) const

    {

        return a.h<h;

    }

};

priority_queue<Tree> que;

int Astar(int s,int t,int k)

{

    int cnt = 0;

    while(!que.empty())

        que.pop();

    if(s==t)

        k++;

    if(dis[s]==inf)

        return -1;

    Tree no,next;

    no = (Tree){s,0,dis[s]};

    que.push(no);

    while(!que.empty())

    {

        no = que.top();

        que.pop();

        //printf("%d %d %d \n",no.v,no.len,no.h);

        if(no.v == t)

            cnt++;

        if(cnt==k)

            return no.len;

        for(int i=0;i<rg[no.v].size();i++)

        {

            Node tmp = rg[no.v][i];

            next.v = tmp.to;

            next.len = no.len + tmp.val;

            next.h = next.len + dis[tmp.to];

            que.push(next);

        }

    }

    return -1;

}

void Clear(int x)

{

    for(int i=0;i<=x;i++){

        g[i].clear();

        rg[i].clear();

    }

}

int main()

{

    //freopen("Input.txt","r",stdin);

    while(~scanf("%d%d",&n,&m))

    {

        for(int i=0;i<m;i++)

        {

            int x,y,z;

            scanf("%d%d%d",&x,&y,&z);

            g[y].push_back((Node){x,z});

            rg[x].push_back((Node){y,z});

        }

        int s,t,k;

        scanf("%d%d%d",&s,&t,&k);

        SPFA(t);

        int ans = Astar(s,t,k);

        printf("%d\n",ans);

        Clear(n);

    }

    return 0;

}