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;
}