迷宫

发表于

迷宫

题意：给n个点和m条无向边，求1到n的次短路。

方法一

对于次短路，之前我是没学过的，模拟赛遇到此题，想了半天怎么实现，想出了自己的独特方法：

对于每个点我们都保存起点到它的最短路长度和次短路长度

1
2
3
struct node{
	int fir,sec;
}a[maxn];

像SPFA一样，一旦能更新就入队，但难点在于fir和sec的互相转移。

  1. 首先考虑u的最短路能够更新to的最短路时，即：a[to].fir>a[u].fir+val（val为边权），此时让to的次短路等于to的最短路，to的最短路等于a[u].fir+val
  2. 再考虑to的次短路和u的次短路的更新关系，很容易想到当a[to].sec>a[u].sec+val时直接更新是没有问题的。
  3. 最后时u的最短路介于to的最短路和次短路之间，这里有个前提，必须要在没有操作第一步时才能操作。转移就是：a[to].sec=a[u].fir+val;

以上操作一旦能执行to就要入队，因为它的值被更新了，要用它去更新后面的点。

方法二

看网上的方法，是用最短路算法预处理出每个点到起点和终点的最短路，然后枚举每条边，比较出第二短的路。

实测得方法一跑地比方法二快

代码（方法一）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<cstdio>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
const int maxn=5005,maxm=100005,maxint=1000000000;
int n,m;
queue<int> q;
struct edge{
	int v,w;
	edge(int x,int y){
		v=x,w=y;
	}
};
vector<edge> path[maxn];
struct node{
	int fir,sec;
}a[maxn];
inline void bfs(){
	q.push(1);
	a[1].fir=0;
	a[1].sec=maxint;
	for(int i=2;i<=n;i++){
		a[i].fir=a[i].sec=maxint;
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<(int)path[u].size();i++){
			bool ok=0,ok2=0;
			int val=path[u][i].w;
			int to=path[u][i].v;
			if(a[to].fir>a[u].fir+val){
				a[to].sec=a[to].fir;
				a[to].fir=a[u].fir+val;
				ok=1;
				ok2=1;
			}
			if(a[to].sec>a[u].sec+val){
				a[to].sec=a[u].sec+val;
				ok=1;
			}
			if(!ok2&&a[u].fir+val>a[to].fir&&a[u].fir+val<a[to].sec){
				a[to].sec=a[u].fir+val;
				ok=1;
			}
			if(ok)q.push(to);
		}
	}
}
int main(){
	freopen("maze.in","r",stdin);
	freopen("maze.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int aa,bb,cc;
		scanf("%d%d%d",&aa,&bb,&cc);
		path[aa].push_back(edge(bb,cc));
		path[bb].push_back(edge(aa,cc));
	}
	bfs();
	printf("%d",a[n].sec);
}

你看其实实现并不是很难，除了fir与sec的转化有点思维含量（毕竟考试时只能想出这样无脑的方法，但我跑的就是比std快）