洛谷 P1491 集合位置

题意

给定一张 $n$ 点 $m$ 边的无向图，第 $i$ 个点坐标为 $(x_i,y_i)$，求 $1\to n$ 的非严格次短路（不允许重复经过点和边）。

思路

我们采用删边的思想，先跑一遍最短路，记录路径，然后依次删掉最短路上每条边，分别跑一遍最短路，再取个最小值即可。

为什么这是正确的呢？首先，次短路至少有一条边不属于最短路。其次，我们不用枚举不在最短路上的边，因为删这些边对最短路没有影响。

至于如何删边，不需要直接在邻接表中找到后再删，这没必要，还会超时，只需要在跑最短路的时候，传入两个参数，分别是要删掉的边的两个端点，只要当前边相连的是这两个点，就直接忽略掉（注意无向图）。

typedef double real;
typedef pair<int, double> PID;
typedef pair<double, int> PDI;
const real INF = 1e20;struct Graph{int n;vector<vector<PID>> G;vector<real> dis;vector<int> pre;vector<bool> vis;Graph(int _n): n(_n){G.resize(n);}// Add an undirected edge <u, v> to the graph with edge weight `w`。void insert(int u, int v, real w){G[u].push_back({v, w});G[v].push_back({u, w});}// Starting from s, run the shortest path, ignoring edges (du, dv).// If (du, dv) = (-1, -1), then no edge will be deleted and the path will be recorded in `pre`.void dij(int s, int du = -1, int dv = -1){dis.assign(n, INF);vis.assign(n, false);if(du == -1 && dv == -1) pre.assign(n, -1);priority_queue<PDI, vector<PDI>, greater<PDI>> q;dis[s] = 0.;q.push({0., s});while(q.size()){int u = q.top().second;q.pop();if(vis[u]) continue;vis[u] = true;for(auto &edge: G[u]){int v = edge.first;real w = edge.second;if((du == u && dv == v) || (du == v && dv == u)) continue;if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;q.push({dis[v], v});if(du == -1 && dv == -1) pre[v] = u;}}}}
};

代码

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
#define int long longtypedef double real;
typedef pair<int, double> PID;
typedef pair<double, int> PDI;
const real INF = 1e20;struct Graph{int n;vector<vector<PID>> G;vector<real> dis;vector<int> pre;vector<bool> vis;Graph(int _n): n(_n){G.resize(n);}void insert(int u, int v, real w){G[u].push_back({v, w});G[v].push_back({u, w});}void dij(int s, int du = -1, int dv = -1){dis.assign(n, INF);vis.assign(n, false);if(du == -1 && dv == -1) pre.assign(n, -1);priority_queue<PDI, vector<PDI>, greater<PDI>> q;dis[s] = 0.;q.push({0., s});while(q.size()){int u = q.top().second;q.pop();if(vis[u]) continue;vis[u] = true;for(auto &edge: G[u]){int v = edge.first;real w = edge.second;if((du == u && dv == v) || (du == v && dv == u)) continue;if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;q.push({dis[v], v});if(du == -1 && dv == -1) pre[v] = u;}}}}
};real dist(real x1, real y1, real x2, real y2){real p = x1 - x2, q = y1 - y2;return sqrt(p * p + q * q);
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m;cin >> n >> m;vector<real> x(n), y(n);Graph G(n);for(int i = 0; i < n; i++) cin >> x[i] >> y[i];for(int i = 0, u, v; i < m; i++){cin >> u >> v;u--, v--;real w = dist(x[u], y[u], x[v], y[v]);G.insert(u, v, w);}G.dij(0);real ans = INF;for(int i = n - 1; i; i = G.pre[i]){G.dij(0, i, G.pre[i]);ans = min(ans, G.dis.back());}if(ans >= INF) printf("-1\n");else printf("%.2lf\n", ans);return 0;
}