POJ 2502 建图+spfa模版

#include <cstdio>  
#include <cstring>  
#include <iostream>  
#include <math.h>  
#include <queue>  
#define N 250  
#define M N*N+2  
#define inf64 0x7ffffff  
#define inf 0x7ffffff  
using namespace std;  
  
inline int Min(int a,int b){return a>b?b:a;}  
struct Edge{  
    int f,t,nex;  
    double d;  
}edge[M];  
int head[N],edgenum;  
double dis[N];  
struct node{  
    double x,y;  
}p[N];  
double DIS(node a,node b){return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}  
void addedge(int u,int v,double d){  
    Edge E={u,v,head[u],DIS(p[u],p[v])*6/(d*100)};  
    edge[edgenum]=E;  
    head[u]=edgenum++;  
}  
  
int n;  
void spfa(){  
    int i,u,v;  
    for(i=0;i<=n;i++)dis[i]=inf;  
    bool inq[N]; memset(inq,0,sizeof(inq));  
    dis[1]=0;  
    queue<int>q;  q.push(1);  inq[1]=1;  
    inq[2]=1;  
    while(!q.empty()){  
        u=q.front(); q.pop(); inq[u]=false;  
        for(i=head[u];i!=-1;i=edge[i].nex)  
        {  
            v=edge[i].t;  
            if(dis[v]>dis[u]+edge[i].d)  
            {  
                dis[v]=dis[u]+edge[i].d;  
                if(!inq[v])  
                    q.push(v),inq[v]=1;  
            }  
        }  
    }  
}  
int main()  
{  
    double x,y;  
    memset(head,-1,sizeof(head)); edgenum=0;  
    scanf("%lf %lf %lf %lf",&p[1].x,&p[1].y,&p[2].x,&p[2].y);  
  
    n=3;  
    int now=3;  
    while(~ scanf("%lf%lf",&x,&y))  
        if(x==-1 && y==-1)  
        {  
            for(int i=now;i<n-1;i++)addedge(i,i+1,40),addedge(i+1,i,40);  
            now=n;  
        }  
        else   
        {  
        p[n].x=x, p[n].y=y;  
        n++;  
        }  
  
    for(int i=1;i<n;i++)  
        for(int j=1;j<n;j++)  
            if(i!=j)  
            addedge(i,j,10);  
    spfa();  
    printf("%.0lf\n",dis[2]);  
  
    return 0;  
}  
/* 
0 0 10000 1000 
0 200 5000 200 7000 200 -1 -1  
2000 600 5000 600 10000 600 -1 -1 

*/