http://poj.org/problem?id=3635
题意：有 n 个城市 ，每个 城市的 油价 不一样 ，已知 各 城市之间的距离 ，（假设 一 单位 距离 耗费一单位的 油量）一辆车 的 油箱 最多可以 装 c 升油，求从 s 到 e，的 最小 花费油量，如果不能到达 输出 impossible 。
题解：一开始 自己 写了 个，到达每一点后枚举 可以 增加的 油量 结果 tle （太多 无用的状态了）。。。。。。
dp[i][j] 表示 到达 城市 i 剩余油量 为 j 的 最小花费；
首先到达每个城市的后 要加的 油量 是 不确定 的 ，所以 我们要 将 每一个城市 拆成 c+ 1 个点，（不是直接的拆分），在 每一个 状态节点 我们有 两种选择 ，1 ： 油量 加 1 （这个 就 相当于 拆分 成了 c+1 个节点）；2：不加油 直接 走向 可 扩展的节点 。
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-12
15 #define inf 0x7fffffff
16
17 //freopen("data.txt","r",stdin);
18 const double pi = acos(-1.0);
19 typedef __int64 ll;
20 const int maxn = 1200 ;
21 using namespace std;
22 struct node
23 {
24
25 int v;
26 int len ;
27 int next ;
28 }p[maxn*10*2] ;
29 struct qnode
30 {
31 int d;
32 int u ;
33 int cost ;
34 qnode(int x,int y,int z):u(x),d(y),cost(z){}
35 friend bool operator < (qnode a,qnode b)
36 {
37 return a.cost > b.cost ;
38 }
39 };
40 int num,a[maxn],next[maxn],dp[maxn][102],n,m,vis[maxn][102];
41 void add(int u ,int v,int len)
42 {
43 p[num].v = v;
44 p[num].len = len ;
45 p[num].next = next[u] ;
46 next[u] = num++;
47 }
48 priority_queue<qnode>que;
49 int bfs(int s,int e,int c)
50 {
51
52 int i , j ;
53 while(!que.empty())que.pop();
54
55 for(i = 0 ; i <= n;i++ )
56 {
57 for(j = 0; j<= c;j++)
58 dp[i][j] = inf ;
59 }
60
61 CL(vis,0);
62
63 dp[s][0] = 0 ;
64
65 que.push(qnode(s,0,0));
66
67 while(!que.empty())
68 {
69 qnode b = que.top();que.pop();
70
71 int u = b.u;
72 int cost = b.cost;
73 int d = b.d ;
74 vis[u][d] = 1;// 标记 已经找到了 的 最小的 ，下面就不用 再扩展的 此节点了
75 if(u == e) return cost ;// 用的是 优先队列 所以 出来的定是 最小的 ；
76
77 if(d+1 <= c &&!vis[u][d + 1] && dp[u][d+1]> dp[u][d] + a[u])//油量 加 1
78 {
79 dp[u][d + 1] = dp[u][d] + a[u] ;
80 que.push(qnode(u,d+1,dp[u][d+1]));
81
82 }
83 for(i = next[u];i!= -1;i = p[i].next)// 直接 走向 相邻 节点 ；
84 {
85 int v = p[i].v ;
86 int len = p[i].len ;
87
88 if(d >= len &&!vis[v][d - len] && dp[v][d - len] > cost)
89 {
90 dp[v][d - len] = cost ;
91 que.push(qnode(v,d - len,cost));
92 }
93
94
95 }
96
97
98 }
99
100
101 return -1 ;
102 }
103 int main()
104 {
105 //freopen("data.txt","r",stdin);
106 int s,e,c,i,x,y,d,q;
107 while(~scanf("%d%d",&n,&m))
108 {
109 for(i = 0;i < n;i++) scanf("%d",&a[i]) ;
110
111 CL(next,-1) ;
112 num = 0 ;
113 for(i = 0 ;i< m;i++)
114 {
115 scanf("%d%d%d",&x,&y,&d);
116 add(x,y,d);
117 add(y,x,d);
118 }
119
120 scanf("%d",&q);
121
122 while(q--)
123 {
124 scanf("%d%d%d",&c,&s,&e);
125 int ans = bfs(s,e,c);
126 if(ans != -1)printf("%d\n",ans);
127 else puts("impossible");
128 }
129 }
130
131 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-12
15 #define inf 0x7fffffff
16
17 //freopen("data.txt","r",stdin);
18 const double pi = acos(-1.0);
19 typedef __int64 ll;
20 const int maxn = 1200 ;
21 using namespace std;
22 struct node
23 {
24
25 int v;
26 int len ;
27 int next ;
28 }p[maxn*10*2] ;
29 struct qnode
30 {
31 int d;
32 int u ;
33 int cost ;
34 qnode(int x,int y,int z):u(x),d(y),cost(z){}
35 friend bool operator < (qnode a,qnode b)
36 {
37 return a.cost > b.cost ;
38 }
39 };
40 int num,a[maxn],next[maxn],dp[maxn][102],n,m,vis[maxn][102];
41 void add(int u ,int v,int len)
42 {
43 p[num].v = v;
44 p[num].len = len ;
45 p[num].next = next[u] ;
46 next[u] = num++;
47 }
48 priority_queue<qnode>que;
49 int bfs(int s,int e,int c)
50 {
51
52 int i , j ;
53 while(!que.empty())que.pop();
54
55 for(i = 0 ; i <= n;i++ )
56 {
57 for(j = 0; j<= c;j++)
58 dp[i][j] = inf ;
59 }
60
61 CL(vis,0);
62
63 dp[s][0] = 0 ;
64
65 que.push(qnode(s,0,0));
66
67 while(!que.empty())
68 {
69 qnode b = que.top();que.pop();
70
71 int u = b.u;
72 int cost = b.cost;
73 int d = b.d ;
74 vis[u][d] = 1;// 标记 已经找到了 的 最小的 ，下面就不用 再扩展的 此节点了
75 if(u == e) return cost ;// 用的是 优先队列 所以 出来的定是 最小的 ；
76
77 if(d+1 <= c &&!vis[u][d + 1] && dp[u][d+1]> dp[u][d] + a[u])//油量 加 1
78 {
79 dp[u][d + 1] = dp[u][d] + a[u] ;
80 que.push(qnode(u,d+1,dp[u][d+1]));
81
82 }
83 for(i = next[u];i!= -1;i = p[i].next)// 直接 走向 相邻 节点 ；
84 {
85 int v = p[i].v ;
86 int len = p[i].len ;
87
88 if(d >= len &&!vis[v][d - len] && dp[v][d - len] > cost)
89 {
90 dp[v][d - len] = cost ;
91 que.push(qnode(v,d - len,cost));
92 }
93
94
95 }
96
97
98 }
99
100
101 return -1 ;
102 }
103 int main()
104 {
105 //freopen("data.txt","r",stdin);
106 int s,e,c,i,x,y,d,q;
107 while(~scanf("%d%d",&n,&m))
108 {
109 for(i = 0;i < n;i++) scanf("%d",&a[i]) ;
110
111 CL(next,-1) ;
112 num = 0 ;
113 for(i = 0 ;i< m;i++)
114 {
115 scanf("%d%d%d",&x,&y,&d);
116 add(x,y,d);
117 add(y,x,d);
118 }
119
120 scanf("%d",&q);
121
122 while(q--)
123 {
124 scanf("%d%d%d",&c,&s,&e);
125 int ans = bfs(s,e,c);
126 if(ans != -1)printf("%d\n",ans);
127 else puts("impossible");
128 }
129 }
130
131 }