参考文献(b站视频):
题目链接
https://www.luogu.com.cn/problem/P2865
题目描述:
贝茜把家搬到了一个小农场,但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景,不想那么快地结束她的旅途,于是她每次回农场,都会选择第二短的路径,而不象我们所习惯的那样,选择最短路。 贝茜所在的乡村有R(1<=R<=100,000)条双向道路,每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1,她的朋友们居住在农场N(即贝茜每次旅行的目的地)。 贝茜选择的第二短的路径中,可以包含任何一条在最短路中出现的道路,并且,一条路可以重复走多次。当然咯,第二短路的长度必须严格大于最短路(可能有多条)的长度,但它的长度必须不大于所有除最短路外的路径的长度。
输入格式:
Line 1: Two space-separated integers: N and R
Lines 2..R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)
输出格式:
Line 1: The length of the second shortest path between node 1 and node N
输入样例:
4 4
1 2 100
2 4 200
2 3 250
3 4 100
输出样例:
450
注意点1:
虽然此为一个稀疏图,只需要用邻接表来存储,不用管是否需要处理重边。但还是应该注意一下。
与存最短路的方式不同,求最短路的时候,如果存在有重边的话,取最小的重编即可。
但是由于求的是次短路,需要将重边也保留下来。如情况:存在1 -> 2 > 3 > 4;以及1 -> 2 -> 3 -> 4.两条路,
1->2->3只有一条路,但是3->存在两条路,两条路都不一样,则1->4的最短路和次短璐分别用上了两个不同的3->4
注意点2:最重要的思路:
使用一个dist1[]存最短路,使用一个dist2[]存次短璐。
一条边u->v
使用dist1[u]和dist2[u]来更新dist1[v]和dist2[v]
1.当dist1[u] + w < dist1[v]的时候,(等于的情况 再此题中无需考虑,没有需要考虑的必要,此题求的是值,不是方案)
则说明可以将dist1[v]更新。
但是dist1[v]为v原先的最短路,一定比原先的dist2[v]要小,
所以要更新dist1[v],先更新dist2[v]
即dist2[v] = dist1[v]
然后在更新dist1[v] = dist1[u] + w
2. 当dist1[u] + w > dist1[v]时,则dist1[u]无法更新dist1[v]。但是有可能dist1[u] + w < dist2[v]呢。
所以有可能使用dist1[u]更新dist2[v]
则dist2[v] = dist1[u] + w
且要注意,如果条件1满足,则一定不会进入条件2.
因为条件2的前提是dist1[u] + w > dist1[v].如果条件1满足,则dist1[u] + w 都可以用于更新dist1[v]了,又何必用于更新dist2[v]呢。而且条件1满足,则到条件2的时候,dist1[u] + w == dist1[v]使得条件2不满足。
3.还有可能dist2[u] + w < dist2[v]。
为什么dist2[u] + w 不会小于dist1[v]呢?
因为如果dist2[u] + w < dist1[v]的话,条件1中,dist1[u] + w一定就已经 小于 dist1[v]了。轮不到条件3 执行。
所以3执行的情况只可能是 dist2[u] + w < dist2[v].
则dist2[v] = dist2[u] + w;
4.通过一个变量和choose[]变量,判断是否可以进队列。
spfa算法:代码实现
# include <iostream>
# include <cstring>
# include <queue>
using namespace std;
const int N = 5010,R = 2e5 + 10; //双向的
int h[N],e[R],w[R],ne[R],idx;
int dist1[N]; //用于存最短路
int dist2[N]; //用于存次短璐
bool choose[N]; //用于确定此结点是否已经在队列中
queue<int> q; //队列,存被修改的结点值
int n,r;
int spfa()
{
memset(dist1,0x3f,sizeof dist1);
memset(dist2,0x3f,sizeof dist2);
dist1[1] = 0;
choose[1] = true;
q.push(1);
while(q.size())
{
int temp = q.front();
q.pop();
choose[temp] = false;
for(int i = h[temp] ; i != -1 ; i = ne[i])
{
bool push = false;
int j = e[i];
//为什么下面三个if都不考虑等于的情况呢?因为dist1或者2[temp] + w[i] == dist1[j]。但是我们求的次短璐需要长度小于最短路,不能和最短路相等(即就算有多个最短路,其实都当作一个最短路来看待。所以等于dist1[i]毫无意义再此题中,我们求的就是大小,无关方案)。同样,等于dist2[]也毫无意义。
if(dist1[temp] + w[i] < dist1[j]) //dist1[temp]可以更新dist1[j]
{
dist2[j] = dist1[j];
dist1[j] = dist1[temp] + w[i];
push = true;
}
if(dist1[temp] + w[i] > dist1[j] && dist1[temp] + w[i] < dist2[j]) //dist1[temp]无法更新dist1[j],但是可以更新dist2[j].当此第二个if()实现时,说明原来的dist1[temp] + w[i]是大于dist2[j]的,即第一个if无法实现,因为如果第一个if实现,则第二个一定无法实现。即第二个if就是用于 原dist1[temp] +w[i] > dist1[i] ,但是小于dist2[i],于是更新dist2[i]
{
dist2[j] = dist1[temp] + w[i];
push = true;
}
if(dist2[temp] + w[i] < dist2[j]) //从dist2[temp]的话,一定没有办法去更新dist1[i],因为如果dist2[temp]能够更新dist1[i],那么前面的if中dist1[temp]一定已经将dist1[i]更新了。不会轮到dist2[temp]去更新dist1[i].但用dist2[temp]可能可以更新dist2[i].
{
dist2[j] = dist2[temp] + w[i];
push = true;
}
if(push == true && choose[j] == 0)
{
choose[j] = true;
q.push(j);
}
}
}
return dist2[n];
}
void add(int a, int b ,int wei)
{
e[idx] = b;
w[idx] = wei;
ne[idx] = h[a];
h[a] = idx++;
}
//使用邻接表的方式,因为这样就不用管重边
int main()
{
scanf("%d %d",&n,&r);
memset(h,-1,sizeof h);
for(int i = 1 ; i <= r ; i++)
{
int a,b,l;
scanf("%d %d %d",&a,&b,&l);
add(a,b,l);
add(b,a,l);
}
int temp = spfa();
printf("%d\n",temp);
return 0;
}
算法2:使用dijkstra算法求解次短璐。
思路:
其中最重要的思路就是:光dist1[]出队只能代表dist1[]为最短路径,但是dist2[]未必是次短路径。
如果想让dist2[]确定为次短路径,则要确保dist2[]也要出队一次才行。
语法:
参考文献: https://www.cnblogs.com/lpf-666/p/13532549.html
定义小根堆
/*
priority_queue<>变为小根堆:
1.priority_queue<int,vector<int>,greater<int>> q; //即为小根堆
2.priority_queue<>中要注意:
struct Node
{
int d;
bool operator < (const Node &other) const
{
return d > other.d; //小根堆,从小到大排序
// return d < other.d ; //大根堆,从到到小排队
}
}
priority_queue<Node>; //小根堆
*/
dijkstra代码实现:
# include <iostream>
# include <queue>
# include <cstring>
using namespace std;
const int N = 5010 , R = 200010;
struct Node
{
int u , d , idx; // u起点,d为距离,idx为0,1
bool operator < (const Node &other) const
{
return d > other.d;
}
};
int h[N],e[R],ne[R],w[R],idx;
priority_queue<Node> q;
int dist[N][2];
int choose[N][2];
int n,r;
void add(int a , int b , int wei)
{
e[idx] = b;
w[idx] = wei;
ne[idx] = h[a];
h[a] = idx++;
}
void dij()
{
memset(dist,0x3f,sizeof dist);
dist[1][0] = 0;
q.push({1,0,0});
while(!q.empty())
{
auto t = q.top();
q.pop();
if(choose[t.u][t.idx])
{
continue;
}
choose[t.u][t.idx] = 1;
for(int i = h[t.u] ; i != -1 ; i = ne[i])
{
int j = e[i];
int wei = w[i];
if(dist[t.u][0] + wei < dist[j][0]) //3个if只会用其中一个if()
{
dist[j][1] = dist[j][0];
dist[j][0] = dist[t.u][0] + wei;
q.push({j,dist[j][0],0});
q.push({j,dist[j][1],1});
}
if(dist[t.u][0] + wei > dist[j][0] && dist[t.u][0] + wei < dist[j][1])
{
dist[j][1] = dist[t.u][0] +wei;
q.push({j,dist[j][1],1});
}
if(dist[t.u][1] +wei < dist[j][1])
{
dist[j][1] = dist[t.u][1] + wei;
q.push({j,dist[j][1],1});
}
}
}
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d %d",&n,&r);
for(int i = 1 ; i <= r ; i++)
{
int a,b,wei;
scanf("%d %d %d",&a,&b,&wei);
add(a,b,wei);
add(b,a,wei);
}
dij();
printf("%d\n",dist[n][1]);
return 0;
}