POJ 2449 Remmarguts' Date【K短路问题，A*、dijkstra】

POJ 2449 Remmarguts' Date
http://poj.org/problem?id=2449
算法核心：A*、dijkstra
大意：求有向图中从s到t的k短路
分析:
1.用dijkstra逆向计算出所有点到t的最短距离dis[i]
2.建立估价函数 f(i)= g(i)+h(i)
  其中g(i)为从s到i的实际距离，h(i)为从i到t的最短路dis[i]
3.使用上述估计函数用A*算法从s点出发BFS全图，用visited[i]表示点i的出队次数。
  当visited[i]=k时，即找到从s到t的k短路为f(i)
  其间若visited[i]>k则放弃该点

4.注意：若s==t,需 k+1;

#include<stdio.h>
#include<string.h>
#include<queue>
usingnamespace std;
constint N =1000+1;
constint M =100000+1;
struct Edge
{
 int from,to;
 int dis;
 Edge *next;
}*ed[N],edge[M],*re[N],redge[M];
int ednum;
int dis[N];
int visited[N];
void init(int n)
{
 int i;
 for(i=0;i<n;i++)
 {
  ed[i]=NULL;
     re[i]=NULL;
 }
}
void addEdge(int from,int to,int dis)
{
 Edge *ptr =&edge[ednum];
 ptr->from = from;
 ptr->to = to;
 ptr->dis = dis;
 ptr->next = ed[from];
 ed[from]=ptr;
}

void addRedge(int from,int to,int dis)
{
 Edge *ptr =&redge[ednum];
 ptr->from = from;
 ptr->to = to;
 ptr->dis = dis;
 ptr->next = re[from];
 re[from]=ptr;
}

struct dnode//dijkstra()优先队列中使用的节点
{
 int v,len;//记录从出发点到节点v的长度
booloperator<(const dnode &A)const
 {
  return A.len<len;
 }
};

void dijkstra(int s,int n)//计算各点到终点的距离
{
 memset(visited,0,sizeof(visited));
    memset(dis,-1,sizeof(dis));
 priority_queue<dnode>Q;
 dnode cur,next;
 cur.len =0;
 cur.v = s;
 Q.push(cur);
 dis[s]=0;
 int vnum =0;//已访完的节点数
while(!Q.empty())
 {
  cur = Q.top();

  Q.pop();
  if(visited[cur.v])continue;
  visited[cur.v]=1;
  vnum++;
  if(vnum==n)return;
  for(Edge *ed = re[cur.v];ed!=NULL;ed=ed->next)
  {
           if(visited[ed->to]==0)
     {
      if(dis[ed->to]==-1||dis[ed->to]>cur.len+ed->dis)
      {
       next.len = cur.len+ed->dis;
       dis[ed->to]=next.len;
       next.v = ed->to;
       Q.push(next);
      }
     }
  }

 }
     
}

struct anode//astar()优先队列中的节点
{
   int to;   //记录从出发点到当前节点的距离
int len;
   booloperator<(const anode &A)const
   {
    if(dis[A.to]==-1)returnfalse;
    if(dis[to]==-1)returntrue;
    return A.len+dis[A.to]<len+dis[to];//估计函数的使用
   }
};
int aStar(int from,int to,int k)
{
     memset(visited,0,sizeof(visited));

  priority_queue<anode>Q;
  anode cur,next;
  if(from==to)k++;//两点重合时按题意加1
  cur.len =0;
  cur.to = from;
  Q.push(cur);
  while(!Q.empty())
  {
         cur = Q.top();
 // printf("%d\n",cur.len);
   Q.pop();
   if(visited[cur.to]==k)return cur.len+dis[cur.to];
   if(visited[cur.to]>k)continue;
   visited[cur.to]++;
   if(visited[to]==k)return cur.len;

   for(Edge *ptr = ed[cur.to];ptr;ptr=ptr->next)
   {
    next.len = cur.len+ptr->dis;
    next.to = ptr->to;
    Q.push(next);
   }

  }
   return-1;
}
int main()
{
 int n,m;
 while(scanf("%d%d",&n,&m)!=EOF)
 {
  init(n);
  ednum =0;
  while(m--)
  {
   int a,b,t;
   scanf("%d%d%d",&a,&b,&t);
   a--;
   b--;
   addEdge(a,b,t);
   addRedge(b,a,t);
   ednum++;
  }
  int s,t,k;
  scanf("%d%d%d",&s,&t,&k);
  s--,t--;
  dijkstra(t,n);
 // for(int i=0;i<n;i++)
 //  printf("%d\n",dis[i]);

  if(dis[s]==-1)printf("-1\n");
  else
   printf("%d\n",aStar(s,t,k));
 }
 return0;
}