PWRFAIL - Mất điện
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#define INF 1e11
#define MAX 10101
#define w first
#define v second
using namespace std;
typedef pair<double,int> di;
int n;
bool d[MAX][MAX];
vector<di> g[MAX];
int x[MAX];
int y[MAX];
double md[MAX];
void loadgraph(void) {
double m,t;
int i,j,k,u,v;
scanf("%d",&n);
scanf("%d",&k);
scanf("%lf",&m);
for (i=1;i<=n;i=i+1) {
scanf("%d",&x[i]);
scanf("%d",&y[i]);
}
for (i=1;i<=k;i=i+1) {
scanf("%d",&u);
scanf("%d",&v);
d[u][v]=true;
d[v][u]=true;
}
for (i=1;i<n;i=i+1)
for (j=i+1;j<=n;j=j+1) {
if (d[i][j]) {
g[i].push_back(di(0,j));
g[j].push_back(di(0,i));
}
else {
t=hypot(x[i]-x[j],y[i]-y[j]);
if (t<=m) {
g[i].push_back(di(t,j));
g[j].push_back(di(t,i));
}
}
}
for (i=2;i<=n;i=i+1) md[i]=INF;
md[1]=0;
}
void dijkstra(void) {
priority_queue<di,vector<di>,greater<di> > q;
di x;
int i,u;
double d;
q.push(di(0,1));
while (!q.empty()) {
x=q.top();q.pop();
u=x.v;d=x.w;
for (i=0;i<g[u].size();i=i+1)
if (d+g[u][i].w<md[g[u][i].v]) {
md[g[u][i].v]=d+g[u][i].w;
q.push(di(md[g[u][i].v],g[u][i].v));
}
}
if (md[n]>=INF) printf("-1");
else printf("%.0lf",md[n]*1000);
}
int main(void) {
//freopen("tmp.inp","r",stdin);
loadgraph();
dijkstra();
return 0;
}