ACM-ICPC 2018 沈阳赛区网络预赛 E.Made In Heaven（k 短路 / A*+Dijkstra）

Made In Heaven

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 spots in the jail and M roads connecting some of the spots. JOJO finds that Pucci knows the route of the former (K−1)-th shortest path. If Pucci spots JOJO in one of these 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 KK-th quickest path to get to the destination. What's more, JOJO only has T units of time, so she needs to hurry.

JOJO starts from spot S, and the destination is numbered 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 units of time.

Input

There are at most 50 test cases.

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

The second line contains four numbers S, E, K and T (1≤S,E≤N, 1≤K≤10000,1≤T≤100000000).

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

It is guaranteed that for any two spots there will be only one directed road from spot A to spot B(1≤A,B≤N,A≠B), but it is possible that both directed road <A,B> and directed road <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).

样例输入复制

样例输出复制

yareyaredawa

题目来源

ACM-ICPC 2018 沈阳赛区网络预赛

链接

https://nanti.jisuanke.com/t/31445

题意

n个点m条边有向带权图，问从s到t的k短路的时间是否小于等于时间Time。

题解

A*算法模板题，可以参考：传送门。但是据说如果S无法到T然后跑A*算法的话会超时，所以首先需要特判一下，就这个地方比赛的时候写chuo了导致TLE，还以为出题人卡了啥，太菜了太菜了。

当时的处理是在跑A*的时候特判一下if (tmp.c + dist[u] > Time) return -1; // 超时直接返回-1，后面自己再测了一下，加了这个快了大概一倍。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;
int n, m, s, t, k, Time;
bool vis[maxn];
int dist[maxn];

struct Node
{
    int v, c;
    Node (int _v = 0, int _c = 0): v(_v), c(_c) {}
    bool operator < (const Node &rhs) const
    {
        return c + dist[v] > rhs.c + dist[rhs.v]; // 估价函数 fx = gx + hx 路径短先出队
    }
};

struct Edge
{
    int to, cost;
    Edge (int _to = 0, int _cost = 0): to(_to), cost(_cost) {}
};

vector <Edge> E[maxn], revE[maxn];

void addedge(int u, int v, int w)
{
    E[v].push_back(Edge(u, w)); // 反向加边
    revE[u].push_back(Edge(v, w)); // 正向加边
}

void dijkstra(int s, int n) // 最短路
{
    for (int i = 0; i <= n; ++i)
    {
        vis[i] = false;
        dist[i] = inf;
    }
    dist[s] = 0;
    priority_queue <Node> Q;
    Q.push(Node(s, dist[s]));
    while (!Q.empty())
    {
        Node tmp = Q.top();
        Q.pop();
        int u = tmp.v;
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = 0; i < E[u].size(); ++i)
        {
            int v = E[u][i].to, cost = E[u][i].cost;
            if (!vis[v] && dist[v] > dist[u] + cost)
            {
                dist[v] = dist[u] + cost;
                Q.push(Node(v, dist[v]));
            }
        }
    }
}

int astar(int s)
{
    if (dist[s] == inf) // 不能到达
        return -1;
    priority_queue <Node> Q;
    Q.push(Node(s, 0));
    k--;
    while (!Q.empty())
    {
        Node tmp = Q.top();
        Q.pop();
        int u = tmp.v;
        if (tmp.c + dist[u] > Time) // 超时直接返回-1，可不要
            return  -1;
        if (u == t)
        {
            if (k)
                --k;
            else  // 第k次到达目标节点t
                return tmp.c;
        }
        for (int i = 0; i < revE[u].size(); ++i)
        {
            int v = revE[u][i].to, cost = revE[u][i].cost;
            Q.push(Node(v, tmp.c + cost));
        }
    }
    return -1;
}

int main()
{
    int u, v, w;
    while (scanf("%d%d", &n, &m) != EOF)
    {
        scanf("%d%d%d%d", &s, &t, &k, &Time);
        for (int i = 0; i <= n; ++i)
        {
            E[i].clear();
            revE[i].clear();
        }
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
        }
        dijkstra(t, n); // t点到所有点的最短路
        int ans = astar(s);
        if (ans == -1 || ans > Time) // 无法到达或者超过时间
            printf("Whitesnake!\n");
        else
            printf("yareyaredawa\n");
    }
    return 0;
}

*

The end.
2018-09-09 星期日