典型的最短路问题，但是多了一个条件，就是每个点属于一个layer,相邻的layer移动，如x层移到x+1层需要花费c.
一种显而易见的转化是我把这些边都建出来，但是最后可能会使得边变成O(n^2);
网上看到的一些做法就是拆点，假如我给每层做一个平台点，所有点都可以到这个平台，然后再换乘到别的平台里不就可以了吗？ 所以对于属于第i层的点我们构造一个i层点的虚拟点，把这些点连到这个平台点，花费为0，相邻平台点之间的花费为c不就可以了吗？ 但是问题就出现在这里了，这样的话同一层的点的花费就会变成0，原本可能不可达的变得可达。网上看到的拆点方法有这么两种。
A.每层拆两个点，一个点管入，一个点管出，这样的话同层的点不会回到同层的另外一个点上。
B.每层拆一个点，这个点只管入，而处于该层的点则向左右两层点相连。
A的话新建了2n个点，4n条边（两层相邻2n,每个点对应两条边2n,2n+2n＝4n），B的话新建了n个点，5n条边（平台间2n条，每个点2n条，平台到点n条）。
不知道上面有没算错请指正。具体参考了下面的博客：
http://www.baidu.com/link?url=MV7krOHUY-l_IgU1_R5qKyUVgL5ZRprWE1IznI82Vwoo_RG_LrIaqxvCJismujP2TVaEEFg607BdhwWeUEy5aa
http://www.cnblogs.com/kuangbin/archive/2013/09/11/3315071.html
这道题当作是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
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<cmath>#include<algorithm>#include<queue>#define ll long long#define maxn 300150#define maxm 700100#define inf 0x3f3f3f3fusing
namespace std;int
first[maxn];int
nxt[maxm];int
e;int
vv[maxm];int
cost[maxm];int
n, m, c;int
layer[maxn];int
dis[maxn];bool
in[maxn];void
addedge(int
u, int
v, int
w){ vv[e] = v; cost[e] = w; nxt[e] = first[u]; first[u] = e++;}void
spfa(int
s){ queue<int> q; memset(in, 0, sizeof(in)); memset(dis, 0x3f, sizeof(dis)); q.push(s); dis[s] = 0; in[s] = true; while
(!q.empty()){ int
u = q.front(); q.pop(); in[u] = false; for
(int i = first[u]; i != -1; i=nxt[i]){ int
v = vv[i]; if
(dis[v] > dis[u] + cost[i]){ dis[v] = dis[u] + cost[i]; if
(!in[v]) q.push(v), in[v] = true; } } }}int
vlayer[maxn];int
main(){ int
T; cin >> T; int
ca = 0; while
(T--) { e = 0; memset(first, -1, sizeof(first)); memset(vlayer, 0, sizeof(vlayer)); scanf("%d%d%d", &n, &m, &c); for
(int i = 1; i <= n; i++){ scanf("%d", layer + i); vlayer[layer[i]] = 1; } for
(int i = 1; i <= n-1; i++){ if
(vlayer[i] && vlayer[i + 1]){ addedge(n + i, n + i + 1, c); addedge(n + i + 1, n + i, c); } } for
(int i = 1; i <= n; i++){ addedge(n + layer[i], i, 0); if
(layer[i] > 1) addedge(i, n+layer[i] - 1, c); if
(layer[i] < n) addedge(i, n+layer[i] + 1, c); } int
ui, vi, wi; for
(int i = 0; i < m; i++){ scanf("%d%d%d", &ui, &vi, &wi); addedge(ui, vi, wi); addedge(vi, ui, wi); } spfa(1); int
ans = dis[n]; if
(ans<inf) printf("Case #%d: %d\n",++ca, dis[n]); else
printf("Case #%d: %d\n", ++ca, -1); } return
0;} |
HDU4725 The Shortest Path in Nya Graph SPFA最短路
原文：http://www.cnblogs.com/chanme/p/3565753.html