F: Minefield

There is a minefield in front of your backyard and you do not want to make it your graveyard whenever you try to get pass through it! Your task is to find out if one can cross the minefield, from one corner to the opposite one, without blowing up within certain constraint on the walking distance through the field. In addition to the walking distance constraint, the only available information is a set of points in the minefield that are safe, i.e. places where you can put your foot on without activating a landmine. You can move from one safe point to another safe point if their distance is at most 1.5 meters far from each other.

Input 

The input consists of several test cases. Each test case starts with a line specifying the size of the mineland with two integers w and h separated by a blank corresponding, respectively, to the width and the height in meters of a rectangular landmine, 1 w, h 10000 . The next line specifies n , the number of safe points, with 0 n 10000 . The following n lines contain safe point coordinates x and y , separated by a blank, which are floating point numbers with 0 x w and 0 y h . The n + 1 line contains a floating point number d 1.5 corresponding to the constraint on the walking distance. The end of the test cases is indicated with a line with one * character. All floating point numbers are given with exactly two decimal figures.

Output 

One line per test case, preserving the input order. Each output line corresponds to

I am lucky!

if there is a safe path of distance at most d from (0, 0) to (w, h) , or to

Boom!

otherwise. You can always assume that the points (0, 0) and (w, h) are safe points.

Sample Input 

5 4
7
1.00 1.00
1.00 2.00
2.00 1.00
2.00 2.00
3.00 3.00
4.00 2.00
5.00 3.00
8.50
5 4
8
1.00 1.00
1.00 2.00
2.00 1.00
2.00 2.00
3.00 3.00
4.00 2.00
5.00 3.00
5.00 4.00
7.90
*

Sample output 

I am lucky!
Boom!

---

題目說明：

從 (0,0) 出發，每次移動最多 1.5 公尺(歐幾里得距離)，最後要達到 (w,h)，
中間會有幾個中繼的安全點，而詢問能不能在指定總步長小於等於 d.

題目解法：

由於點數很多，用 O(n*n) 建表就準備吞 TLE，對 x 座標做升排序，然後建表的時候就比較容易些，接著使用 spfa 去跑一次最短路檢查即可。

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct Pt {
    long long x, y;
    Pt(long long a, long long b):x(a), y(b){}
    Pt():x(0), y(0){}
#define eps 1e-8
    bool operator<(const Pt &a) const {
        if(x != a.x)
            return x < a.x;
        return y < a.y;
    }
};
Pt D[10005];
vector<pair<int, double> > g[10005];
double dis[10005];
int used[10005];
void spfa(double d, int st, int ed, int n) {
    int i, tn, y;
    double v;
    for(i = 0; i < n; i++) {
        dis[i] = d+514;
        used[i] = 0;
    }
    queue<int> Q;
    Q.push(st);
    dis[st] = 0;
    while(!Q.empty()) {
        tn = Q.front(), Q.pop();
        used[tn] = 0;
        for(vector<pair<int, double> >::iterator it = g[tn].begin();
            it != g[tn].end(); it++) {
            y = it->first, v = it->second;
            if(dis[y] > dis[tn] + v && dis[tn]+v <= d) {
                dis[y] = dis[tn]+v;
                if(used[y] == 0) {
                    Q.push(y);
                    used[y] = 1;
                }
            }
        }
    }
    if(dis[ed] <= d)
        puts("I am lucky!");
    else
        puts("Boom!");

}
int main() {
    int w, h, n;
    int i, j, k;
    long long x, y, a, b;
    double d;
    while(scanf("%d %d", &w, &h) == 2) {
        scanf("%d", &n);
        for(i = 0; i < n; i++) {
            scanf("%lld.%lld %lld.%lld", &x, &y, &a, &b);
            D[i] = Pt(x*100+y, a*100+b);
        }
        D[n++] = Pt(0, 0);
        D[n++] = Pt(w*100, h*100);
        sort(D, D+n);
        for(i = 0; i < n; i++)
            g[i].clear();
        for(i = 0; i < n; i++) {
            for(j = i+1; j < n; j++) {
                if(D[j].x-D[i].x > 150)
                    break;
                if((D[j].x-D[i].x)*(D[j].x-D[i].x)+
                   (D[j].y-D[i].y)*(D[j].y-D[i].y) <= 150*150) {
                   g[i].push_back(make_pair(j, sqrt((D[j].x-D[i].x)*(D[j].x-D[i].x)+
                   (D[j].y-D[i].y)*(D[j].y-D[i].y))/100));
                   g[j].push_back(make_pair(i, sqrt((D[j].x-D[i].x)*(D[j].x-D[i].x)+
                   (D[j].y-D[i].y)*(D[j].y-D[i].y))/100));
                }
            }
        }
        scanf("%lf", &d);
        spfa(d, 0, n-1, n);
    }
    return 0;
}