PWRFAIL - Mất điện
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <cmath>
using namespace std;
int n, m;
double maxd;
int x[1010], y[1010];
bool a[1010][1010], inS[1010];
double d[1010];
int main() {
scanf("%d%d", &n, &m);
scanf("%lf", &maxd);
for(int i=0;i<n;++i)
scanf("%d%d", &x[i], &y[i]);
for(int i=0;i<m;++i) {
int u, v;
scanf("%d%d", &u, &v);
--u; --v;
a[u][v] = a[v][u] = true;
}
for(int i=0;i<n;++i) d[i] = 1e11;
d[0] = 0;
while(true) {
int imin = -1;
double min = 1e11;
for(int i=0;i<n;++i) if(!inS[i] && d[i] < min) {
min = d[i];
imin = i;
}
if(imin==-1) break;
inS[imin] = true;
for(int j=0;j<n;++j) {
double cost;
if(a[imin][j]) cost = 0;
else {
cost = sqrt((x[imin]-x[j])*1.0*(x[imin]-x[j]) + (y[imin]-y[j])*1.0*(y[imin]-y[j]));
if(cost - 1e-10 > maxd) cost = 1e11;
}
if(d[j] > d[imin] + cost) {
d[j] = d[imin] + cost;
}
}
}
if(d[n-1] < 1e10) printf("%d\n", (int)(d[n-1] * 1000 + 1e-10));
else printf("-1\n");
// system("pause");
return 0;
}