参考了http://blog.myspace.cn/e/404763245.htm
1 /*
2 **下面给出自己写的邻接表形式采用SPFA计算启发函数的效率表示一般的K短路代码
3 **表示可以当成模板,这个不是最好的代码, 不过一般情况下都可以的吧,现在去尝试下用A*做迷宫问题.据说效率不是一般的高
4 **/
5 #include <iostream> 6 #include <queue>
7 #include <cstring>
8 #include <cstdio>
9 using namespace std;
10 #define MAXV 1001
11 #define MAXE 100000
12 #define INF 100000000
13
14 typedef struct {
15
16 int v;
17 int val;
18 int next;
19 }Edge;
20
21 Edge e[MAXE];
22 int p[MAXV], eid, n;
23
24 void add(int u, int v, int val) {
25
26 e[eid].next = p[ u ];
27 e[eid].v = v;
28 e[eid].val = val;
29 p[u] = eid ++;
30 }
31
32 //建立反向图 为了计算启发函数h(x)(即结点x到T的最短距离)
33 Edge op[MAXE];
34 int oph[MAXV], opid;
35
36 void addop(int u, int v, int val) {
37
38 op[opid].next = oph[ u ];
39 op[opid].v = v;
40 op[opid].val = val;
41 oph[ u ] = opid ++;
42 }
43
44
45 int dis[MAXV], S, T, K;
46
47 struct Node {
48
49 int v;
50 int val;
51 friend bool operator <(Node a, Node b) {
52
53 return a.val + dis[a.v] > b.val + dis[b.v];
54 }
55 };
56
57 void init() {
58
59 for(int i = 0; i <= n; ++ i) {
60
61 p[ i ] = -1;
62 dis[ i ] = INF;
63 oph[ i ] = -1;
64 }
65 eid = 0;
66 opid = 0;
67 }
68
69 void spfa() {
70
71 dis[ T ] = 0;
72 queue<int> Q;
73 Q.push(T);
74 while(!Q.empty()) {
75
76 int u = Q.front();
77 Q.pop();
78
79 for(int j = oph[ u ]; j != -1; j = op[ j ].next) {
80
81 int v = op[ j ].v;
82 int val = op[ j ].val;
83 if(dis[ v ] > dis[ u ] + val) {
84
85 dis[ v ] = dis[ u ] + val;
86 Q.push(v);
87 }
88 }
89 }
90 }
91
92 void A_star() {
93
94 spfa();
95 int vist[MAXV];
96 if(dis[S] == INF) {
97
98 puts("-1");
99 return ;
100 }
101 memset(vist, 0, sizeof(vist));
102 priority_queue<Node> Q;
103 Node t;
104 t.v = S;
105 t.val = 0;
106 Q.push(t);
107 int u;
108 int val;
109 while(!Q.empty()) {
110
111 t = Q.top();
112 Q.pop();
113 u = t.v;
114 val = t.val;
115
116 vist[ u ] ++;
117
118 if(vist[ u ] > K) continue;
119 if(u == T && vist[ u ] == K) break;
120
121 for(int j = p[ u ]; j != -1; j = e[ j ].next) {
122
123 t.v = e[ j ].v;
124 t.val = val + e[ j ].val;
125 Q.push(t);
126 }
127 }
128 if(u == T && vist[ u ] == K) {
129
130 printf("%d\n", val);
131 return ;
132 }
133
134 puts("-1");
135 }
136
137 int main() {
138
139 int m;
140 while(~scanf("%d %d", &n, &m)) {
141
142 init();
143 while(m --) {
144
145 int u, v, val;
146 scanf("%d %d %d", &u, &v, &val);
147 add(u, v, val);
148 addop(v, u, val);
149 }
150 scanf("%d %d %d", &S, &T, &K);
151 if(S == T) K ++;
152 A_star();
153 }
154 return 0;
155 }
/**//*表示上面写的不是SPFA, 貌似是BFS+DP,现在改正一下,效率提高了一点*/
void spfa() 
{
bool vist[MAXV];
memset(vist, false, sizeof(vist));
dis[ T ] = 0;
queue<int> Q;
Q.push(T);
while(!Q.empty()) {
int u = Q.front();
Q.pop();
vist[ u ] = false;
for(int j = oph[ u ]; j != -1; j = op[ j ].next) {
int v = op[ j ].v;
int val = op[ j ].val;
if(dis[ v ] > dis[ u ] + val) {
dis[ v ] = dis[ u ] + val;
if(!vist[ v ]) {
vist[ v ] = true;
Q.push(v);
}
}
}
}
}
struct Point {
int v;
int val;
friend bool operator <(Point a, Point b) {
return a.val > b.val;
}
};
void dijkstra() {
bool vist[MAXV];
int u;
memset(vist, false, sizeof(vist));
priority_queue<Point> Q;
Point t;
t.v = T; t.val = 0; Q.push(t);
while(!Q.empty()) {
t = Q.top(); Q.pop();
u = t.v;
if(vist[ u ]) continue;
vist[ u ] = true;
dis[ u ] = t.val;
for(int j = oph[ u ]; j != -1; j = op[ j ].next) {
int v = op[ j ].v;
if(!vist[ v ]) {
int val = op[ j ].val;
Point tmp;
tmp.v = v;
tmp.val = t.val + val;
Q.push(tmp);
}
}
}
}三者的效率SPFA最高,dijkstra次之,BFS+dp最慢;如果代码有可以优化的地方请留言,谢谢