P1491 集合位置

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
double z,w[200005],dist[200005];
double minn1,lesss,ans1=21374404;
int path[100000],cnt,num,n,m,x,y,v[200005],nxt[200005],head[200005],pre[200005],edge[200005],a[200005],b[200005];
bool vis[200005];
void add(int a,int b,double c)
{
    v[++cnt]=b;
    w[cnt]=c;
    nxt[cnt]=head[a];
    head[a]=cnt;
}
void spfa(int s)
{
    for(int i=1;i<=n;i++)dist[i]=336860180;
    queue<int>q;
    q.push(s);
    dist[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int c=q.front();
        q.pop();
        vis[c]=0;
        for(int i=head[c];i;i=nxt[i])
        {
            int y=v[i];
            if(dist[y]>dist[c]+w[i])
            {
                pre[y]=i;edge[y]=c;
                dist[y]=dist[c]+w[i];
                if(!vis[y])
                {
                    q.push(y);
                    vis[y]=1;
                }
            }
        }
    }
}
double num1(int s,int q)
{
    return sqrt((a[s]-a[q])*(a[s]-a[q])+(b[s]-b[q])*(b[s]-b[q]));
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	cin>>a[i]>>b[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        z=num1(x,y);
        add(x,y,z);
        add(y,x,z);
    }
    spfa(1);
    minn1=dist[n];
    int now=n;
    while(now!=1)
    {
        path[++num]=pre[now];
        now=edge[now];
    }
    for(int i=1;i<=num;i++)
    {
        double s=w[path[i]];
        w[path[i]]=99999999;
        spfa(1);
        lesss=dist[n];
        ans1=min(ans1,lesss);
        w[path[i]]=s;
    }
    if(ans1==21374404)cout<<"-1";
    else printf("%.2lf",ans1);
    return 0;
}