求次短路
很好想，在spfa的基础上添加一个数组即可，就是转移的时候要注意。
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
| void spfa(int u){
for(int i=1;i<=n;i++){
d[i]=inf;d2[i]=inf;
}
d[u] = 0;
q.push(u);
while(!q.empty()){
int x = q.front();q.pop();
inque[x]=false;
for (int i=0;i<g[x].size();i++){
edge son=g[x][i];
if(d[x]+son.w<d2[son.v]){
if(d[x]+son.w==d2[son.v])continue;
if(d[x]+son.w<d[son.v]){
d2[son.v] = d[son.v];
d[son.v] = d[x]+son.w;
}
else if(d[x]+son.w>=d[son.v])d2[son.v] = d[x]+son.w;
if(!inque[son.v]){
q.push(son.v);
inque[son.v]=true;
}
}
}
}
}
|
这份代码是有问题的，注意这几一句。
1
2
3
| if(d[x]+son.w<d2[son.v])
if(d[x]+son.w<d[son.v])
else if(d[x]+son.w>=d[son.v])
|
我们考虑了这几种情况
- x的d可以更新son的d2
- x的d可以更新son的d
- x的d2可以更新son的d不用考虑，因为此时用x的d更新肯定更优。
但是明细我们考虑掉了x的d2可以更新son的d2的情况。
这种情况是不能省略的。
的确，用x的d更新son的d2也一定更优，但是x的d可能不能更新son的d2，即这就是最短路，根据题目要求，它是不能作为次短路的。
所以这种情况必须考虑。
加上
1
| if(d2[x]+son.w<d2[son.v]) d2[son.v] = d2[x]+son.w;
|
即可。
完整代码
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
| #include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
const int inf=INT_MAX/2;
struct edge{
int v,w;
edge(int a=0,int b=0){
v=a;w=b;
}
};
vector <edge> g[maxn];
int inque[maxn];
int d[maxn];
int d2[maxn];
int n,m;
int x,y,c;
queue<int> q;
void spfa(int u){
for(int i=1;i<=n;i++){
d[i]=inf;d2[i]=inf;
}
d[u] = 0;
q.push(u);
while(!q.empty()){
int x = q.front();q.pop();
inque[x]=false;
for (int i=0;i<g[x].size();i++){
edge son=g[x][i];
if(d[x]+son.w<d2[son.v]){
if(d[x]+son.w==d2[son.v])continue;
if(d[x]+son.w<d[son.v]){
d2[son.v] = d[son.v];
d[son.v] = d[x]+son.w;
}
else if(d[x]+son.w>d[son.v])d2[son.v] = d[x]+son.w;
else if(d2[x]+son.w<d2[son.v]) d2[son.v] = d2[x]+son.w;
if(!inque[son.v]){
q.push(son.v);
inque[son.v]=true;
}
}
}
}
}
int main(){
cin>>n>>m;
for (int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&c);
g[x].push_back(edge(y,c));
g[y].push_back(edge(x,c));
}
spfa(1);
cout<<d2[n];
return 0;
}
|