学步园

思路：用的是第k短路算法 A* 具体详解看前一篇 poj 2449 这里就不注释了，都差不多的

//2604K   
282MS
#include <stdio.h>
#include <string.h>
#include <queue>
#define EM 100010
#define VM 5050
const int inf = 0x3f3f3f3f;
using namespace std;

int src,des,n,e;
int head[VM],dis[VM];

struct E
{
    int
to,w,nxt;
} edge[2*EM];

struct data
{
    int
to,g,h;
    bool
operator < (data a) const
    {
       
return a.g + a.h < g + h;
    }
};

void addedge (int cu,int cv,int cw)
{
    edge[e].to =
cv;
    edge[e].w =
cw;
    edge[e].nxt
= head[cu];
    head[cu] = e
++;
}

void dij ()
{
    int
i,j,k;
    bool
vis[VM];
    memset
(vis,false,sizeof(vis));
    memset
(dis,0x3f,sizeof(dis));
    dis[des] =
0;
    for (i = 1;
i <= n; i ++)
    {
       
int min = inf;
       
for (j = 1; j <= n; j ++)
           
if (!vis[j]&&dis[j]
< min)
           
{
               
min = dis[j];
               
k = j;
           
}
       
vis[k] = true;
       
for (int u = head[k]; u != -1; u = edge[u].nxt)
       
{
           
int v = edge[u].to;
           
if (!vis[v]&&dis[v]
> dis[k] + edge[u].w)
               
dis[v] = dis[k] + edge[u].w;
       
}
    }
}

int Astar ()
{
    int
cnt[VM];
    data
cur,nxt;
   
priority_queue <data> node;
    memset
(cnt,0,sizeof (cnt));
    cur.to =
src;
    cur.g =
0;
    cur.h =
dis[src];
    node.push
(cur);

    while
(!node.empty ())
    {
       
cur = node.top ();
       
node.pop ();