洛谷 P1491 集合位置

题意

给定一张 $n$ 点 $m$ 边的无向图，第 $i$ 个点坐标为 $x_i,y_i)$ ，求 $\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 long

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);
	}
	
	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;
}