poj 2449 Remmarguts' Date【第K短路】

题意：求点s 到点t 的第 k 短路的距离；

估价函数=当前值+当前位置到终点的距离

f(n)=g(n)+h(n); g(n)表示g当前从s到p所走的路径的长度, h(n)‘启发式函数’，表示为终点t到其余一点p的路径长度；

(1)将有向图的所有边反向,以原终点t为源点,求解t到所有点的最短距离;
(2)新建一个优先队列,将源点s加入到队列中;
(3)从优先级队列中弹出f(p)最小的点p,如果点p就是t,则计算t出队的次数;
如果当前为t的第k次出队,则当前路径的长度就是s到t的第k短路的长度,算法结束;
否则遍历与p相连的所有的边,将扩展出的到p的邻接点信息加入到优先级队列;

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int Maxn = 10010;
const int INF = 1e9;

struct node{
    int to,val;
    node(){}
    node(int a,int b)
    {
        to = a; val = b;
    }
};

vector<node> adj[Maxn],_adj[Maxn];

int n,m,k;
bool vis[Maxn];
int dis[Maxn];

void AddEdge(int x,int y,int val)
{
    adj[x].push_back(node(y,val));
    _adj[y].push_back(node(x,val));//反向存图
}
void Dijkstra(int s,int t)
{
    priority_queue<int, vector<int>,greater<int> > q;
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++)
        vis[i]=false,dis[i]=INF;
    vis[t]=true;dis[t]=0;q.push(t);
    int u,len;
    while(!q.empty())
    {
        u = q.top(); q.pop();
        len = _adj[u].size();
        for(int i=0;i<len;i++)
        {
            node v = _adj[u][i];
            if(dis[v.to]>dis[u]+v.val)
            {
                dis[v.to]=dis[u]+v.val;
                if(!vis[v.to])
                {
                    q.push(v.to);
                    vis[v.to]=true;
                }
            }
        }
        vis[u]= false;
    }
}
struct Anode{
    int h,g,id;
    Anode(int a,int b,int c){h=a;g=b;id=c;}
    bool operator < (Anode a) const{
        return h+g > a.h + a.g;
    }
};
priority_queue<Anode> Q;
int Astar(int s,int t)    //A*算法
{
    while(!Q.empty()) Q.pop();
    Q.push(Anode(0,dis[s],s));
    int len,num;
    num=0;
    while(!Q.empty())
    {
        Anode u = Q.top();
        Q.pop();
        if(u.id==t) ++num;
        if(num>=k) return u.h;
        len = adj[u.id].size();
        for(int i=0;i<len;i++)
        {
            node v = adj[u.id][i];
            Q.push(Anode(u.h+v.val,dis[v.to],v.to));
        }
    }
    return -1;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=-1)
    {
        for(int i=0;i<Maxn;i++)
            adj[i].clear(),_adj[i].clear();
        int x,y,v,s,t;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&v);
            AddEdge(x,y,v);
        }
        scanf("%d%d%d",&s,&t,&k);
        if(s==t) k++;
        Dijkstra(s,t);
        printf("%d
",Astar(s,t));
    }
    return 0;
}
/*
2 2
1 2 5
2 1 4
1 2 2
*/