很早之前听说有一种dp是在图上的dp，然后是在跑SPFA的时候进行dp，所以特地找了一题关于在SPFA的时候dp的。
题意：1~a是村庄 a+1~a+b是城堡，存在m条无向边。求由a+b->1的最短路，但是你有很多飞鞋，每双飞鞋可以跑一个固定的距离l,但是跑的时候要是碰到了城堡就要停下来，而且也不能停在路中间。
思路和代码参考了下面的这个网址：http://blog.csdn.net/acm_cxlove/article/details/8679230
思路：正常来说我们就跑SPFA就可以了，每次从队列里取点更新，但因为有了跑鞋，所以每次取点的时候还有多一种转移途径，因此我们就需要知道每次用了跑鞋之后从当前的点能够到达哪些点，这个时候我们就需要两点之间的距离，因为两点之间不能经过城堡，所以在跑SPFA的时候我们对于那些城堡的点我们就不再压入的跑SPFA.然后当dis[u][v]<=l的时候我们就可以转移了。
|
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114 |
#pragma warning(disable:4996)#include<cstring>#include<cstdio>#include<iostream>#include<string>#include<algorithm>#include<vector>#include<queue>#define maxn 120#define maxm 120*120#define inf 0x3f3f3f3fusing
namespace std;int
a, b, m, l, k;struct
Edge{ int
u, v, w; Edge(){} Edge(int
ui, int
vi, int
wi) :u(ui), v(vi), w(wi){}}e[maxm];int
ecnt;int
dis[maxn][maxn];int
vis[maxn];int
first[maxn];int
nxt[maxm];void
add(int
u, int
v, int
w){ e[ecnt].u = u; e[ecnt].v = v; e[ecnt].w = w; nxt[ecnt] = first[u]; first[u] = ecnt++;}void
spfa(){ memset(dis, 0x3f, sizeof(dis)); queue<int> que; for
(int loc = 1; loc <= a + b; loc++){ while
(!que.empty()) que.pop(); memset(vis, 0, sizeof(vis)); que.push(loc); vis[loc] = 1; dis[loc][loc] = 0; while
(!que.empty()){ int
u = que.front(); que.pop(); vis[u] = 0; for
(int i = first[u]; i != -1; i = nxt[i]){ int
v = e[i].v, w = e[i].w; if
(dis[loc][v] > dis[loc][u] + w){ dis[loc][v] = dis[loc][u] + w; if
(v <= a&&!vis[v]){ que.push(v); vis[v] = 1; } } } } }}int
dp[maxn][15];int
main(){ int
T; cin >> T; while
(T--) { scanf("%d%d%d%d%d", &a, &b, &m, &l, &k); memset(first, -1, sizeof(first)); ecnt = 0; int
ui, vi, wi; for
(int i = 0; i < m; i++){ scanf("%d%d%d", &ui, &vi, &wi); add(ui, vi, wi); add(vi, ui, wi); } spfa(); memset(dp, 0x3f, sizeof(dp)); memset(vis, 0, sizeof(vis)); queue<int> que; que.push(a + b); dp[a + b][k] = 0; vis[a + b] = 1; while
(!que.empty()){ int
u = que.front(); que.pop(); vis[u] = 0; for
(int sh = 0; sh <= k; sh++){ for
(int i = first[u]; i != -1; i = nxt[i]){ int
v = e[i].v, w = e[i].w; if
(dp[v][sh] > dp[u][sh] + w){ dp[v][sh] = dp[u][sh] + w; if
(!vis[v]){ que.push(v); vis[v] = 1; } } } if
(!sh) continue; for
(int v = 1; v <= a + b; v++){ if
(u != v&&dis[u][v] <= l){ if
(dp[v][sh - 1] > dp[u][sh]){ dp[v][sh - 1] = dp[u][sh]; if
(!vis[v]){ que.push(v); vis[v] = 1; } } } } } } int
ans = inf; for
(int i = 0; i <= k; i++){ ans = min(ans, dp[1][i]); } printf("%d\n", ans); } return
0;} |
---恢复内容结束---
ZOJ1232 Adventure of Super Mario spfa上的dp
原文：http://www.cnblogs.com/chanme/p/3568059.html