PWRFAIL - Mất điện

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;

const int N = 1000 + 5;
const double EPS = 1e-6;
typedef pair<double, int> di;

double d[N][N], m, dd[N];
bool rem[N][N];
int n, x[N], y[N], w;

void enter() {
    scanf("%d%d%lf", &n, &w, &m);
    for(int i = 0; i < n; ++i) scanf("%d%d", x+i, y+i);
    for(int i = 0, u, v; i < w; ++i) {
        scanf("%d%d", &u, &v); --u; --v;
        rem[u][v] = rem[v][u] = 1;
    }
}

double sqr(const double &x) { return x * x; }

void solve() {
    for(int i = 0; i < n; ++i) {
        d[i][i] = 1000000000;
        for(int j = i + 1; j < n; ++j)
            if(rem[i][j] == 0) {
                double v = sqrt(sqr(x[i] - x[j]) + sqr(y[i] - y[j]));
                d[i][j] = d[j][i] = v + EPS < m ? v : 1000000000;
            }
        dd[i] = 1000000000;
    }
    priority_queue<di, vector<di>, greater<di> > q; q.push(di(0, 0)); dd[0] = 0;
    while(!q.empty()) {
        double du = q.top().first; int u = q.top().second; q.pop();
        if(du > dd[u] + EPS) continue;
        for(int v = 0; v < n; ++v) if(dd[v] > du + d[u][v] + EPS)
            q.push(di(dd[v] = du + d[u][v], v));
    }
    printf("%d\n", dd[n-1] >= 1000000000 ? -1 : int(dd[n-1] * 1000));
}

int main() {
    enter();
    solve();
    return 0;
}

Download