• 题意：

  • 就是给出一个有向图，问你从起点到终点的第k短路。

  • 题解：

  • 用到第k短路+A*启发式搜索

  • 代码：

    #include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
int N,M,S,K,End,T;
struct Edge{
  int to,w,next;
}E[100*MAXN],RE[100*MAXN];//正向边，Astar用。反向边，Spfa用。
int head[MAXN],rhead[MAXN];
int tot;
struct A{
  int f,g,id;//id是点的号。
  //Astar核心式子：f=g+h,这里h(i)=dis[i]。
  bool operator < (const A &b)const {
      if(f == b.f)return  g < b.g;
      return f > b.f;
  }
};
void Add(int from,int to,int w){
  E[++tot].to = to;
  E[tot].w = w;
  E[tot].next = head[from];
  head[from] = tot;
  RE[tot].to = from;
  RE[tot].w = w;
  RE[tot].next = rhead[to];
  rhead[to] = tot;
}
int dis[MAXN];
bool used[MAXN];
/*求出终点到各点的最短长度dis[i]
然后用这个长度来作为后面A*算法的启发式信息h(i)。*/
void Spfa(int from){
  memset(dis,INF,sizeof dis);
  //memset(used,false,sizeof used);
  dis[from] = 0;
  queue<int> Q;
  Q.push(from);
  used[from] = true;
  while(!Q.empty()){
      int t = Q.front();
      Q.pop();
      used[t] = false;
      for(int i=rhead[t] ; i ; i=RE[i].next){
          if(dis[RE[i].to] > dis[t] + RE[i].w){
              dis[RE[i].to] = dis[t] + RE[i].w;
              if(!used[RE[i].to]){
                  used[RE[i].to] = true;
                  Q.push(RE[i].to);
              }
          }
      }
  }
}
//A* 启发式搜索
int Astar(int from,int to){
  int cnt = 0;
  priority_queue<A> Q;
  if(from == to)++K;//坑点，注意判断题意中相同点算不算最短路
  if(dis[from] == INF)return -1;//起点与终点不连通。
  A t,tt;
  t.id = from,t.g = 0,t.f = t.g + dis[from];
  Q.push(t);
  while(!Q.empty()){
      tt = Q.top();
      Q.pop();
      if(tt.id == to){
          ++cnt;
          if(cnt == K)return tt.g;//第K次到达时就是结果。
      }
      for(int i=head[tt.id] ; i ; i=E[i].next){
          t.id = E[i].to;
          t.g = tt.g + E[i].w;
          t.f = t.g + dis[t.id];
          Q.push(t);
      }
  }
  return -1;//没有第K短路
}
void init(){
  tot = 0;
  memset(head,0,sizeof head);
  memset(rhead,0,sizeof rhead);
}
int main(){

  while(scanf("%d %d",&N,&M) == 2){
      init();
      scanf("%d %d %d %d",&S,&End,&K,&T);//起点 终点 第k短路
      int x,y,w;
      for(int i=1 ; i<=M ; ++i){
          scanf("%d %d %d",&x,&y,&w);//有一条从x指向y的边权值为w
          Add(x,y,w);
      }
      Spfa(End);
      int re = Astar(S,End);
      if(re <= T && re != -1)printf("yareyaredawa\n");
      else printf("Whitesnake!\n");
  }
  return 0;
}

```