Description
贝茜把家搬到了一个小农场，但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。 贝茜所在的乡村有R(1<=R<=100,000)条双向道路，每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1，她的朋友们居住在农场N（即贝茜每次旅行的目的地）。 贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。
Output
- 第1行: 输出一个整数，即从农场1到农场N的第二短路的长度
4 4
1 2 100
2 4 200
2 3 250
3 4 100
Sample Output
450
输出说明:
最短路：1 -> 2 -> 4 (长度为100+200=300)
第二短路：1 -> 2 -> 3 -> 4 (长度为100+250+100=450)
Solution
裸严格次短路，用SPFA维护到每个点的最短和次短路。用u来更新v时，注意如果到v的最短路等于到u的最短路加u,v路径长度的话，要检查v的次短路！（WA了一发。。。）
Code
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
64
65
66
67
68
69
70
| #include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
struct edge_type {
int to, next, w;
} edge[200010];
int dis[5100], din[5100], cnte, h[5100];
void ins(int x, int y, int z) {
edge[++cnte].to = y;
edge[cnte].next = h[x];
edge[cnte].w = z;
h[x] = cnte;
}
queue<int> Q;
int n, m;
bool vis[5100];
void SPFA() {
for (int i = 1; i <= n; ++i) dis[i] = din[i] = INF;
dis[1] = 0; Q.push(1); vis[1] = true; int now;
while (!Q.empty()) {
now = Q.front(); Q.pop(); vis[now] = false;
for (int i = h[now]; i; i = edge[i].next) {
int v = edge[i].to;
if (dis[v] > dis[now] + edge[i].w) {
din[v] = dis[v];
dis[v] = dis[now] + edge[i].w;
if (!vis[v]) {
vis[v] = true;
Q.push(v);
}
} else {
if (dis[v] == dis[now] + edge[i].w) {
din[v] = min(din[v], din[now] + edge[i].w);
if (!vis[v]) {
vis[v] = true;
Q.push(v);
}
} else {
if (din[v] > dis[now] + edge[i].w) {
din[v] = dis[now] + edge[i].w;
if (!vis[v]) {
vis[v] = true;
Q.push(v);
}
}
}
}
}
}
}
int main() {
n = getint(); m = getint(); int x, y, z;
while (m--) {
x = getint(); y = getint(); z = getint();
ins(x, y, z);
ins(y, x, z);
}
SPFA();
printf("%d", din[n]);
return 0;
}
|