P1491 集合位置

#include<bits/stdc++.h>
using namespace std;
#define edge(i,x) for(int i=h[x],y; i; i=to[i].nt)
#define ll long long
const int N=200001;
struct node{
    double x,y;
    void read(){
        cin>>x>>y;
        return;
    }
};
struct edges{
    int nt,to;
    double w;
};
int h[N];
edges to[N*2];
node nd[N];
int n,m,cnt;
void add(int x,int y,double z)
{
    to[++cnt]=(edges){h[x],y,z};
    h[x]=cnt;
}
double dis(int x,int y)
{
    return sqrt((nd[x].x-nd[y].x)*(nd[x].x-nd[y].x)+(nd[x].y-nd[y].y)*(nd[x].y-nd[y].y));
}
int p[N],total;
double ans=10000000;
namespace dijkstra{
    double d[N];
    int ps[N];
    int vis[N];
    #define pii pair < int , int >
    #define mp make_pair
    priority_queue < pii , vector < pii > , greater < pii > > q;
    void dijkstra(int u,int v)
    {
        while(!q.empty())q.pop();
        for(int i=1; i<=n; i++)
        {
            d[i]=1000000000000;vis[i]=0;
        }
        d[1]=0;
        q.push(mp(0,1));
        while(!q.empty())
        {
            int x=q.top().second;
            if(vis[x])continue;
            q.pop();
            vis[x]=1;
            edge(i,x){
                double z;
                y=to[i].to;z=to[i].w;
                if(x==u&&y==v||x==v&&y==u)continue;
                if(d[y]>d[x]+z){
                    ps[y]=x;
                    d[y]=d[x]+z;
                    q.push(mp(d[y],y));
                }
            }
        }
        if(u==-1&&v==-1)
        {
            for(int i=n; i; i=ps[i])p[++total]=i;
           // for(int i=1; i<=total; i++)printf("%d ",p[i]);
            //cout<<endl;
        }else
        {
            ans=min(ans,d[n]);
        }
        //cout<<d[n]<<endl;

    }
}
int main()
{
    //freopen("text.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)nd[i].read();
    for(int i=1; i<=m; i++)
    {
        static int x,y;
        static double z;
        cin>>x>>y;
        z=dis(x,y);
        add(x,y,z);
        add(y,x,z);
    }
    dijkstra::dijkstra(-1,-1);
    for(int i=1; i<total; i++)
    {
        dijkstra::dijkstra(p[i],p[i+1]);
    }
    printf("%.2lf\n",ans);
    return 0;
}