次短路
概念：次短路是相对于最短路的，简单来说就是第二短的路径。
方法：
d
i
j
k
s
t
r
a
dijkstra
dijkstra 找最短路的同时，维护一个次短路数组(
d
i
s
t
2
[
]
dist2[]
dist2[])。
- 当 （到达目的节点的最短路）
>
>
> （从队列中取出的值 + 当前点到目的点的距离）即
d
i
s
t
[
v
]
>
d
+
E
[
n
o
w
]
[
i
]
.
c
o
s
t
dist[v] > d + E[now][i].cost
dist[v]>d+E[now][i].cost，则更新最短路和次短路， 即
d
i
s
t
2
[
v
]
=
d
i
s
t
[
v
]
;
dist2[v] = dist[v];
dist2[v]=dist[v];
d
i
s
t
[
v
]
=
d
+
E
[
n
o
w
]
[
i
]
.
c
o
s
t
;
dist[v] = d + E[now][i].cost;
dist[v]=d+E[now][i].cost; - 当 （到达目的节点的最短路）
<
<
< （从队列中取出的值 + 当前点到目的点的距离）
<
<
< （到达目的节点的次短路），只更新次短路，即
d
i
s
t
2
[
v
]
=
d
+
E
[
n
o
w
]
[
i
]
.
c
o
s
t
;
dist2[v] = d + E[now][i].cost;
dist2[v]=d+E[now][i].cost;
注意：每次更新结束后都需要加入队列。
放
道
水
题
A
C
代
码
放道水题AC代码
放道水题AC代码
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 5100;
struct edge {
int to, cost;
bool operator < (const edge &d) const{
return cost > d.cost;
}
};
std::vector<edge > E[MAXN];
void add_edge(int u, int v, int c) {
E[u].push_back((edge){v, c});
}
int N, R, a, b, d;
int dist[MAXN];
int dist2[MAXN];
int dijkstra(int s) {
memset(dist, INF, sizeof(dist));
fill(dist2, dist2+N, INF);
priority_queue<edge > pq;
dist[s] = 0;
pq.push((edge){s, dist[s]});
while(!pq.empty()) {
int now = pq.top().to;
int d = pq.top().cost;
pq.pop();
if(dist2[now] < d) continue;
for (int i = 0; i < E[now].size(); ++i) {
int v = E[now][i].to;
int d2 = d + E[now][i].cost;
if(dist[v] > d2) {
dist2[v] = dist[v];
dist[v] = d2;
pq.push((edge){v, dist[v]});
}
else if(dist[v] < d2) {
if(dist2[v] > d2) {
dist2[v] = d2;
pq.push((edge){v, dist2[v]});
}
}
}
}
}
int main(int argc, char const *argv[])
{
cin>>N>>R;
for (int i = 0; i < R; ++i) {
cin>>a>>b>>d;
add_edge(a, b, d);
add_edge(b, a, d);
}
dijkstra(1);
cout<<dist2[N]<<endl;
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
