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

Download