具体思路:在正向图求一边最短路，然后反向边求一边，然后枚举每条边，看删除这个边后是否满足答案。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 10010, M = 400010;
int h[N],rh[N],e[M],ne[M],idx;
double w[M], d1[N],d2[N];
bool st[N];
int n,m;
PII a[N];

double get_dist(int i,int j)
{
    int dx = a[i].x - a[j].x;
    int dy = a[i].y - a[j].y;
    return sqrt(dx * dx + dy * dy);
}

void add(int h[],int a,int b,double c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

void spfa(int h[],double dist[],int start)
{
    memset(st,false,sizeof st);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    
    while(q.size())
    {
        int t = q.front();q.pop();
        st[t] = false;

        for(int i = h[t]; ~ i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(! st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    memset(rh,-1,sizeof rh);

    for(int i = 1; i <= n; i ++) 
    {
        scanf("%d%d",&a[i].x, &a[i].y);
        d1[i] = d2[i] = 1e9;
    }
    for(int i = 1; i <= m; i ++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        double c = get_dist(a,b);
        //printf("%f ",c);
        add(h,a,b,c);add(h,b,a,c);
        add(rh,a,b,c),add(rh,b,a,c);
    }

    spfa(h,d1,1);
    spfa(rh,d2,n);
    double ans = 1e9;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = h[i]; ~ j; j = ne[j])
        {
            int k = e[j];
            double minv = d1[i] + w[j] + d2[k];
            if(minv > d1[n] && ans > minv) ans = minv;
        }
    }
    if(ans == 1e9) cout << -1 << endl;
    else printf("%.2f",ans);
}