Luogu P1491 集合位置

題意：在一個n個點的坐标系中有些點之間有連邊，求次短路

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
const double inf = 1e9;
struct node {
    int next, to;
    double dis;
}edge[A];
int head[A], num_edge;
double dis[A], ans = inf;
bool vis[A];
int n, m, x, y, xx[A], yy[A], pre[A];
void add_edge(int from, int to, double dis) {
    edge[++num_edge].next = head[from];
    edge[num_edge].to = to;
    edge[num_edge].dis = dis;
    head[from] = num_edge;
}
void spfa(int del1, int del2) {
    for (int i = 1; i <= n; i++) dis[i] = inf;
    memset(vis, 0, sizeof vis);
    queue<int> q;
    q.push(1); dis[1] = 0; vis[1] = 1;
    while (!q.empty()) {
        int fr = q.front();
        q.pop(); vis[fr] = 0;
        for (int i = head[fr]; i; i = edge[i].next) {
            int ca = edge[i].to;
            if ((fr == del1 and ca == del2) or (fr == del2 and ca == del1)) continue;
            if (dis[ca] > dis[fr] + edge[i].dis) {
                dis[ca] = dis[fr] + edge[i].dis;
                if (del1 == -1 and del2 == -1) pre[ca] = fr;
                if (!vis[ca]) {
                    vis[ca] = 1;
                    q.push(ca);
                }
            }
        }
    }
}
double calc(int a1, int b1, int a2, int b2) {
    return sqrt((a1 - a2) * (a1 - a2) + (b1 - b2) * (b1 - b2));
}

int main(int argc, char const *argv[])
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> xx[i] >> yy[i];
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        double we = calc(xx[x], yy[x], xx[y], yy[y]);
        add_edge(x, y, we); add_edge(y, x, we);
    }
    spfa(-1, -1);
    int now = n;
    while (pre[now]) {
        spfa(pre[now], now);
        ans = min(ans, dis[n]);
        now = pre[now];
    }
    if (ans == 0x3f) puts("-1");
    else cout << fixed << setprecision(2) << ans << endl;
    return 0;
}