poj 2449 第k短路径

思路：

利用一个估计函数g[i]=dis[i]+len。其中len为队列出来的点当前已经走了的距离。dis[i]为该点到终点的最短路径。这样我们只要将点按g[i]的升序在队列你排序，每次取出最小的g[i]值的点。其意义就是每次找最短的能到终点的点。第一次找到就是最短路径，第二次就是就是第二短，第三次就是...顺推

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<queue>

#define Maxn 1010

#define Maxm 200200

#define inf 10000000

using namespace std;

int dis[Maxn],vi[Maxn],head[Maxn],e,map[Maxn][Maxn],n,m,cnt[Maxn];

struct Edge{

    int u,v,next,val;

}edge[Maxm];

struct Point{

    int u,len;

    int operator <(const Point &temp) const

    {

        return len+dis[u]>temp.len+dis[temp.u];

    }

};

void init()

{

    e=;

    memset(dis,,sizeof(dis));

    memset(vi,,sizeof(vi));

    memset(head,-,sizeof(head));

    memset(cnt,,sizeof(cnt));

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=n;j++)

            map[i][j]=inf;

    }

}

void add(int u,int v,int val)

{

    edge[e].v=v;edge[e].val=val;edge[e].next=head[u];head[u]=e++;

    map[v][u]=(val<map[v][u]?val:map[v][u]);

}

void dijkstra(int s)

{

    int i,j,u;

    for(int i=;i<=n;i++)

        dis[i]=inf,vi[i]=;

    for(i=;i<=n;i++)

        dis[i]=map[s][i];

    dis[s]=;

    for(i=;i<=n;i++)

    {

        int min=inf;

        for(j=;j<=n;j++)

            if(!vi[j] && dis[j]<=min)

            {

                u=j;

                min=dis[j];

            }

        if(min==inf) break;

        vi[u]=;

        for(j=;j<=n;j++)

        {

            if(!vi[j]&&dis[j]>dis[u]+map[u][j])

                dis[j]=dis[u]+map[u][j];

        }

    }

}

int A_star(int s,int t,int k)

{

    priority_queue<Point> q;

    memset(vi,,sizeof(vi));

    Point a,p;

    a.u=s,a.len=;

    q.push(a);

    while(!q.empty())

    {

        a=q.top();

        q.pop();

        vi[a.u]++;

        if(vi[a.u]>k) continue;

        if(vi[t]==k) return a.len;

        for(int v=head[a.u];v!=-;v=edge[v].next)

        {

            p.u=edge[v].v;

            p.len=a.len+edge[v].val;

            q.push(p);

        }

    }

    return -;

}

int main()

{

    int i,j,s,t,k,a,b,c;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        init();

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

        {

            scanf("%d%d%d",&a,&b,&c);

            add(a,b,c);

        }

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

        dijkstra(t);

        if(s==t)

            k++;

        if(dis[s]==inf)

        {

            printf("-1\n");

            continue;

        }

        printf("%d\n",A_star(s,t,k));

    }

    return ;

}