优先队列bfs求最短路
1 /*
2 * File: PKU 3635 Full Tank?
3 * Author: xiaotian @ hnu
4 * Created on 2010年10月8日, 下午4:27
5 * 题解：优先队列bfs
6 */
7 #include<iostream>
8 #include<math.h>
9 #include<queue>
10 #include<stdio.h>
11 #include<algorithm>
12 #include<string.h>
13 #include<vector>
14 using namespace std;
15 #define N 1008
16 #define inf 0x7fffffff
17
18 struct node {
19 int v, dist;
20
21 node(int a = 0, int b = 0) : v(a), dist(b) {
22 }
23 };
24
25 struct Node {
26 int v,rest,cost;
27
28 Node(int a = 0, int b = 0, int c = 0) : v(a), rest(b), cost(c) {
29 }
30 bool operator<(const Node &r) const{
31 return r.cost < cost;
32 }
33 };
34 vector<node>g[N];
35 int dp[N][102];
36 bool vist[N][102];
37 int n, m, a[N], V, S, T, ans;
38 priority_queue<Node>q;
39
40 int bfs() {
41 int x, y, z;
42 while (!q.empty())
43 q.pop();
44 q.push(Node(S, 0, 0));
45 dp[S][0] = 0;
46 while (!q.empty()) {
47 Node p = q.top();
48 q.pop();
49 x = p.v, y = p.rest, z = p.cost;
50 vist[x][y] = 1;
51 if (x == T) return z;
52 if (y + 1 <= V && !vist[x][y + 1] && dp[x][y + 1] > dp[x][y] + a[x]) {
53 dp[x][y + 1] = dp[x][y] + a[x];
54 q.push(Node(x, y + 1, dp[x][y + 1]));
55 }
56 for (int i = 0; i < g[x].size(); i++) {
57 int t = g[x][i].v;
58 int k = y - g[x][i].dist;
59 if (k >= 0 && !vist[t][k] && z < dp[t][k]) {
60 dp[t][k] = z;
61 q.push(Node(t, k, dp[t][k]));
62 }
63 }
64 }
65 return -1;
66 }
67
68 int main() {
69 int i, j;
70 while (scanf("%d%d", &n, &m) != EOF) {
71 for (i = 0; i < n; i++) {
72 scanf("%d", &a[i]);
73 g[i].clear();
74 }
75 int u, v, w;
76 for (i = 0; i < m; i++) {
77 scanf("%d%d%d", &u, &v, &w);
78 g[u].push_back(node(v, w));
79 g[v].push_back(node(u, w));
80 }
81 int tc;
82 scanf("%d", &tc);
83 while (tc--) {
84 scanf("%d%d%d", &V, &S, &T);
85 memset(vist, 0, sizeof (vist));
86 for (i = 0; i < n; i++)
87 for (j = 0; j <= 100; j++)
88 dp[i][j] = inf;
89 ans = bfs();
90 if (ans == -1)
91 printf("impossible\n");
92 else
93 printf("%d\n", ans);
94 }
95 }
96 return 0;
97 }