PWRFAIL - Mất điện
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
//#include <conio.h>
#include <cmath>
#include <iostream>
#define max 1000000000
using namespace std;
struct diem { int x,y; };
double kc(diem A,diem B)
{
return sqrt(((long long)(A.x)-B.x)*((long long)A.x-B.x)+((long long)A.y-B.y)*(A.y-(long long)B.y));
}
double min(double u,double v)
{
if(u<v) return u;
return v;
}
diem A[1010];
double d[1010],m,kq,minn;
int a[1010][1010],n,w,x,y,flag[1010];
long long KQ;
int main()
{
//freopen("matdien.in","r",stdin);
scanf("%d %d",&n,&w);
//printf("%d %d\n",n,w);
scanf("%lf",&m);
for(int i = 1;i<=n;i++)
scanf("%d %d",&A[i].x,&A[i].y);
for(int i = 1;i<=w;i++)
{
scanf("%d %d",&x,&y);
a[x][y] = 1;
a[y][x] = 1;
}
memset(flag,0,sizeof(flag));
for(int i = 0;i<1005;i++) d[i] = max;
int u = 1;
flag[1] = 1;
d[1] = 0;
while(u!=n)
{
//printf("***%d*** %lf\n",u,m);
int vitri;
minn = max;
bool fl = false;
for(int i = 1;i<=n;i++)
{
if(!flag[i])
{
if(a[u][i]==1)
{
d[i] = d[u];
}
if(kc(A[u],A[i])<=m+0.0001)
{
double rich = d[u]+kc(A[u],A[i]);
d[i] = min(d[i],rich);
}
if(d[i]<minn)
{
// printf("%d %lf.....\n",i,d[i]);
vitri = i;
minn = d[i];
fl = true;
}
}
}
u = vitri;
flag[u]=1;
if(!fl) break;
}
kq = d[n];
if(kq >= max)
printf("-1");
else
{
kq = kq*1000;
//if(kq-(long long)kq<0.5)
printf("%lld",(long long)kq);
// else printf("%lld",(long long)kq+1);
}
//getch();
}