计蒜客 ACM-ICPC 2018 沈阳赛区网络预赛 D. Made In Heaven(A*算法第K短路)

Description:

One day in the jail, F·F invites Jolyne Kujo (JOJO in brief) to play tennis with her. However, Pucci the father somehow knows it and wants to stop her. There are $N$N spots in the jail and $M$M roads connecting some of the spots. JOJO finds that Pucci knows the route of the former $(K-1)$(K−1)-th shortest path. If Pucci spots JOJO in one of these $K-1$K−1 routes, Pucci will use his stand Whitesnake and put the disk into JOJO’s body, which means JOJO won’t be able to make it to the destination. So, JOJO needs to take the $K$K-th quickest path to get to the destination. What’s more, JOJO only has $T$T units of time, so she needs to hurry.

JOJO starts from spot $S$S, and the destination is numbered $E$E. It is possible that JOJO’s path contains any spot more than one time. Please tell JOJO whether she can make arrive at the destination using no more than $T$T units of time.

Input:

There are at most $50$50 test cases.

The first line contains two integers $N$N and $M$M $(1\le N\le 1000,0\le M\le 10000)$(1≤N≤1000,0≤M≤10000). Stations are numbered from $1$1 to $N$N.

The second line contains four numbers $S,E,K$S,E,K and $T$T ( $1\le S,E\le N$1≤S,E≤N, $S\ne E$S̸​=E, $1\le K\le 10000$1≤K≤10000, $1\le T\le 100000000$1≤T≤100000000 ).

Then $M$M lines follows, each line containing three numbers $U,V$U,V and $W$W $(1\le U,V\le N,1\le W\le 1000)$(1≤U,V≤N,1≤W≤1000) . It shows that there is a directed road from $U$U-th spot to $V$V-th spot with time $W$W.

It is guaranteed that for any two spots there will be only one directed road from spot $A$A to spot $B$B $(1\le A,B\le N,A\ne B)$(1≤A,B≤N,A̸​=B), but it is possible that both directed road KaTeX parse error: Expected 'EOF', got '&' at position 1: &̲lt;A,B> and directed road KaTeX parse error: Expected 'EOF', got '&' at position 1: &̲lt;B,A> exist.

All the test cases are generated randomly.

Output:

One line containing a sentence. If it is possible for JOJO to arrive at the destination in time, output "yareyaredawa" (without quote), else output "Whitesnake!" (without quote).

Sample Input:

2 2
1 2 2 14
1 2 5
2 1 4

Sample Output:

yareyaredawa

题目链接

判断S到E的第K短路是否小于T，直接套A*算法模板判断第K短路距离。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;

struct Link {
    int V, Weight, Next;
};

Link edges[maxn << 1];
int Head[maxn];
int Tot;
// 反向边
Link Reverseedges[maxn << 1];
int ReverseHead[maxn];
int ReverseTot;

// 链式前向星存图初始化
void Init() {
    Tot = 0;
    memset(Head, -1, sizeof(Head));
    ReverseTot = 0;
    memset(ReverseHead, -1, sizeof(ReverseHead));
}

// 加边建图
void AddEdge(int U, int V, int Weight) {
    edges[++Tot] = Link {V, Weight, Head[U]};
    Head[U] = Tot;
    // 用反向边另建图
    Reverseedges[++ReverseTot] = Link {U, Weight, ReverseHead[V]};
    ReverseHead[V] = ReverseTot;
}

int N, M;
int S, E, K, T;
int Dis[maxn];

struct Cmp {
    bool operator() (const int &A, const int &B) {
        return Dis[A] > Dis[B];
    }
};

// 利用反向边图求各点到终点的最短路
void Dijkstra(int Start) {
    priority_queue<int, vector<int>, Cmp> Que;
    memset(Dis, INF, sizeof(Dis));
    Dis[Start] = 0;
    Que.push(Start);
    while (!Que.empty()) {
        int U = Que.top(); Que.pop();
        for (int i = ReverseHead[U]; i != -1; i = Reverseedges[i].Next) {
            if (Dis[Reverseedges[i].V] > Dis[U] + Reverseedges[i].Weight) {
                Dis[Reverseedges[i].V] = Dis[U] + Reverseedges[i].Weight;
                Que.push(Reverseedges[i].V);
            }
        }
    }
}

struct AStarNode {
    int F, G, Point;
    // A*核心:F=G+H(Point)，这里H(Point)=Dis[Point]
    bool operator < (const AStarNode &A) const {
        if (F == A.F) {
            return G > A.G;
        }
        return F > A.F;
    }
};

// A*算法求第K短路
int AStar(int Start, int End) {
    int Cnt = 0;
    priority_queue<AStarNode> Que;
    // 此题相同点不算最短路
    if (Start == End) {
        K++;
    }
    // 起点与终点不连通
    if (Dis[Start] == INF) {
        return -1;
    }
    Que.push(AStarNode {Dis[Start], 0, Start});
    while (!Que.empty()) {
        AStarNode Keep = Que.top(); Que.pop();
        if (Keep.Point == End) {
            Cnt++;
            if (Cnt == K) {
                // 返回第K短路长度
                return Keep.G;
            }
        }
        for (int i = Head[Keep.Point]; i != -1; i = edges[i].Next) {
            AStarNode Temp;
            Temp.Point = edges[i].V;
            Temp.G = Keep.G + edges[i].Weight;
            Temp.F = Temp.G + Dis[Temp.Point];
            Que.push(Temp);
        }
    }
    return -1;
}

int main(int argc, char *argv[]) {
    while (~scanf("%d%d", &N, &M)) {
        Init();
        scanf("%d%d%d%d", &S, &E, &K, &T);
        for (int i = 0, U, V, C; i < M; ++i) {
            scanf("%d%d%d", &U, &V, &C);
            AddEdge(U, V, C);
        }
        Dijkstra(E);
        int Ans = AStar(S, E);
        if (Ans > T || Ans == -1) {
            printf("Whitesnake!\n");
        }
        else {
            printf("yareyaredawa\n");
        }
    }
    return 0;
}