icpc 2018 沈阳 D-Made In Heaven

• 题意：

• 就是给出一个有向图，问你从起点到终点的第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;
  }
  

```