POJ 2449 Remmarguts' Date(k¶Ì·ģ°å)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 1100
#define maxm 110000
#define inf 0xffffff0
using namespace std;
struct Node{
  int to,w,next;
}Edge[maxm],Edge1[maxm];
int head[maxn],head1[maxn];
struct node{
  int to,g,f;
  bool operator < (const node &a) const{
    if(a.f == f){
      return a.g < g;
    }
    return a.f < f;
  }
};
int dist[maxn];
bool vis[maxn];
int n,m,s,t,k;

void init(){
  memset(Edge,0,sizeof(Edge));
  memset(Edge1,0,sizeof(Edge1));
  memset(head,-1,sizeof(head));
  memset(head1,-1,sizeof(head1));
}

void spfa(int s){
  for(int i=0;i<=n;i++){
    dist[i] = inf;
  }
  memset(vis,false,sizeof(vis));
  vis[s] = 1;
  dist[s] = 0;
  queue<int> q;
  q.push(s);
  while(!q.empty()){
    int u = q.front();
    q.pop();
    vis[u] = false;
    for(int i=head1[u];i!=-1;i=Edge1[i].next){
      int ans = dist[u] + Edge1[i].w;
      if(ans < dist[Edge1[i].to]){
        dist[Edge1[i].to] = ans;
        if(!vis[Edge1[i].to]){
          vis[Edge1[i].to] = 1;
          q.push(Edge1[i].to);
        }
      }
    }
  }
}

int A_Star(){
  node e,ne;
  int cnt = 0;
  priority_queue<node> q;
  if(s == t) k ++;
  if(dist[s] == inf) return -1;
  e.to = s;
  e.g = 0;
  e.f = e.g + dist[e.to];
  q.push(e);
  while(!q.empty()){
    e = q.top();
    q.pop();
    if(e.to == t) cnt ++;
    if(cnt == k) return e.g;

    for(int i=head[e.to];i!=-1;i=Edge[i].next){
      ne.to = Edge[i].to;
      ne.g = e.g + Edge[i].w;
      ne.f = ne.g + dist[ne.to];
      q.push(ne);
    }
  }
  return -1;
}

int main()
{
  while(~scanf("%d%d",&n,&m)){
    init();
    for(int i=0;i<m;i++){
      int u,v,w;
      scanf("%d%d%d",&u,&v,&w);
      Edge[i].to = v;
      Edge[i].w = w;
      Edge[i].next = head[u];
      head[u] = i;

      Edge1[i].to = u;
      Edge1[i].w = w;
      Edge1[i].next = head1[v];
      head1[v] = i;
    }
    scanf("%d%d%d",&s,&t,&k);
    spfa(t);
    int ans = A_Star();
    printf("%d\n",ans);
  }
  return 0;
}