POJ 3635 Full Tank? 【分层图/最短路dp】

Full Tank?

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 8388		Accepted: 2734

Description

After going through the receipts from your car trip through Europe this summer, you realised that the gas prices varied between the cities you visited. Maybe you could have saved some money if you were a bit more clever about where you filled your fuel?

To help other tourists (and save money yourself next time), you want to write a program for finding the cheapest way to travel between cities, filling your tank on the way. We assume that all cars use one unit of fuel per unit of distance, and start with an empty gas tank.

Input

The first line of input gives 1 ≤ n ≤ 1000 and 0 ≤ m ≤ 10000, the number of cities and roads. Then follows a line with n integers 1 ≤ p_i ≤ 100, where p_i is the fuel price in the ith city. Then follow m lines with three integers 0 ≤ u, v < n and 1 ≤ d ≤ 100, telling that there is a road between u and v with length d. Then comes a line with the number 1 ≤ q ≤ 100, giving the number of queries, and q lines with three integers 1 ≤ c ≤ 100, s and e, where c is the fuel capacity of the vehicle, s is the starting city, and e is the goal.

Output

For each query, output the price of the cheapest trip from s to e using a car with the given capacity, or "impossible" if there is no way of getting from s to e with the given car.

Sample Input

5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4

Sample Output

170
impossible

Source

Nordic 2007

题意概括：

有 N 个城市 M 条道路（双向通行），每个城市都有一个加油站（每单位汽油售价分别为 pi ），道路每单位距离花费一单位汽油。求从起点到终点得最小花费（如果不能到达输出-1，因为小车车油箱有容量限制）。

解题思路：

终于还是把这题做了，也忘了是哪一次得集训遇到这道题，是一道好题，可惜当时自己做不出。

这道题正确的打开方式：分层图或者叫最短路dp（个人感觉分层图其实就是搞最短路dp，动态规划的思想）。

状态：dp[ i ][ j ] 到了第 i 个城市还剩下 j 单位的油的最小花费。

状态转移分两种：

1、在当前城市加油（精妙之处在于每次只加 1 单位的油，以最少的油跑最远的地方，如果未来发现这里的油不划算庆幸没有多加而且加到刚刚好，如果未来发现这里的油划算，那就跑回来多加一点咯，因为我们这里是用一个优先队列来保存状态）；　　　　　　　　

2、不加油，直接跑到下一个城市（当然要当前油箱的油可以行驶到下一个城市）；

tip：

注意判重，每种状态只入队一次。

AC code：

  1 //poj 3635 最短路dp
  2 //未优化输入
  3 /*
  4 #include <cstdio>
  5 #include <iostream>
  6 #include <algorithm>
  7 #include <cmath>
  8 #include <queue>
  9 #include <cstring>
 10 #define INF 0x3f3f3f3f
 11 #define LL long long int
 12 using namespace std;
 13 const int MAX_M = 1e4+10;
 14 const int MAX_N = 1e3+10;
 15 const int MAX_K = 105;
 16 struct date
 17 {
 18     int v, nxt, val;
 19 }edge[MAX_M<<1];
 20 
 21 struct node
 22 {
 23     int u, k, w;
 24     bool operator < (const node& a)const{
 25         return w > a.w;
 26     }
 27     node(int a=0, int b=0, int c=0):u(a),k(b),w(c){}
 28 };
 29 int N, M, tank, st, ed;
 30 int coco[MAX_N];
 31 int head[MAX_N], cnt;
 32 int dis[MAX_N][MAX_K];
 33 bool vis[MAX_N][MAX_K];
 34 //priority_queue<node> Q;
 35 
 36 void init()
 37 {
 38     memset(head, -1, sizeof(head));
 39     cnt = 1;
 40 }
 41 
 42 void add(int from, int to, int weight)
 43 {
 44     edge[cnt].nxt = head[from];
 45     edge[cnt].v = to;
 46     edge[cnt].val = weight;
 47     head[from] = cnt++;
 48 }
 49 
 50 void Dijkstra(int s)
 51 {
 52     memset(dis, INF, sizeof(dis));
 53     memset(vis, false, sizeof(vis));
 54     priority_queue<node> Q;
 55     node tp;
 56     tp.u = s, tp.k = 0, dis[s][0] = tp.w = 0;
 57     Q.push(tp);
 58     while(!Q.empty()){
 59         tp = Q.top();Q.pop();
 60         vis[tp.u][tp.k] = true;
 61         if(tp.u == ed){
 62             printf("%d
", tp.w);return;
 63         }
 64 
 65         if(tp.k+1<=tank && !vis[tp.u][tp.k+1] && dis[tp.u][tp.k]+coco[tp.u] < dis[tp.u][tp.k+1]){
 66             dis[tp.u][tp.k+1] = dis[tp.u][tp.k]+coco[tp.u];
 67             Q.push(node(tp.u, tp.k+1, dis[tp.u][tp.k+1]));
 68         }
 69 
 70         for(int i = head[tp.u]; i != -1; i = edge[i].nxt){
 71             int v = edge[i].v, cost = edge[i].val;
 72             if(tp.k >= cost && !vis[v][tp.k-cost] && dis[v][tp.k-cost] > tp.w){
 73                 dis[v][tp.k-cost] = tp.w;
 74                 Q.push(node(v, tp.k-cost, tp.w));
 75             }
 76         }
 77     }
 78     printf("impossible
");
 79 }
 80 
 81 int main()
 82 {
 83     int u, v, w;
 84     scanf("%d%d", &N, &M);
 85     init();
 86     for(int i = 0; i < N; i++){
 87         scanf("%d", &coco[i]);
 88     }
 89     for(int i = 1; i <= M; i++){
 90         scanf("%d%d%d", &u, &v, &w);
 91         add(u, v, w);
 92         add(v, u, w);
 93     }
 94     int T;
 95     scanf("%d", &T);
 96     while(T--){
 97         scanf("%d%d%d", &tank, &st, &ed);
 98         Dijkstra(st);
 99     }
100     return 0;
101 }
102 */
103 
104 
105 //优化输入
106 #include <cstdio>
107 #include <iostream>
108 #include <algorithm>
109 #include <cmath>
110 #include <queue>
111 #include <cstring>
112 #define INF 0x3f3f3f3f
113 #define LL long long int
114 using namespace std;
115 const int MAXN = 1005;
116 const int MAXM = 1e4+10;
117 const int MAXK = 101;
118 int N, M, st, ed, tank;
119 int p[MAXN];   ///每一站的油
120 int cost[MAXN][MAXK];  ///cost[i][j] 到达第i站还剩下j油的最小花费
121 int head[MAXN], cnt;
122 bool vis[MAXN][MAXK];
123 
124 int read()
125 {
126     int f=1, x=0;char ch = getchar();
127     while(ch < '0' || ch > '9') {if(ch=='-')f=-1;ch=getchar();}
128     while(ch >= '0' && ch <= '9') {x = x*10+(ch-'0');ch=getchar();}
129     x=x*f;return x;
130 }
131 struct node
132 {
133     int v, k, val;
134     bool operator < (const node& a)const{
135         return val > a.val;
136     }
137     node(int a=0, int b=0, int c=0):v(a),k(b),val(c){};
138 };
139 
140 struct date
141 {
142     int v, nxt, w;
143 }edge[MAXM<<1];
144 
145 void init()
146 {
147     memset(head, -1, sizeof(head));
148     cnt = 1;
149 }
150 void add(int from, int to, int weight)
151 {
152     edge[cnt].nxt = head[from];
153     edge[cnt].v = to;
154     edge[cnt].w = weight;
155     head[from] = cnt++;
156 }
157 
158 void Dijkstra(int S)
159 {
160     memset(cost, INF, sizeof(cost));
161     memset(vis, false, sizeof(vis));
162     node tp;
163     priority_queue<node> Q;
164     tp.v = S; tp.k = 0; tp.val = 0;
165     Q.push(tp);
166     cost[S][0] = 0;
167     while(!Q.empty()){
168         tp = Q.top(); Q.pop();
169         int fr = tp.v, oil = tp.k;
170         vis[fr][oil] = true;
171         if(fr == ed) {printf("%d
", tp.val);return;}    //因为是优先队列优化的所以到达终点值得第一个值就是最小值
172 
173         if(oil+1 <= tank && !vis[fr][oil+1] && cost[fr][oil+1] > cost[fr][oil]+p[fr]){         ///在当前站一滴一滴地加，最好的情况是加的少跑的远
174             cost[fr][oil+1] = cost[fr][oil]+p[fr];
175             Q.push(node(fr, oil+1, cost[fr][oil+1]));
176         }
177         for(int i = head[fr]; i != -1; i = edge[i].nxt){                                       ///跑到当前的油可以跑到的地方
178             int v = edge[i].v;
179             if(oil >= edge[i].w && !vis[v][oil-edge[i].w] && tp.val < cost[v][oil-edge[i].w]){
180                 cost[v][oil-edge[i].w] = tp.val;
181                 Q.push(node(v, oil-edge[i].w, tp.val));
182             }
183         }
184     }
185     printf("impossible
");
186 }
187 
188 int main()
189 {
190     int u, v, w;
191     //scanf("%d%d", &N, &M);
192     init();
193     N = read(); M = read();
194     //printf("%d %d
", N, M);
195     for(int i = 0; i < N; i++) p[i] = read();
196     for(int i = 1; i <= M; i++){
197         //scanf("%d%d%d", &u, &v, &w);
198         u = read(), v = read(), w = read();
199         add(u, v, w);                         ///无向图
200         add(v, u, w);
201     }
202     int T_case;
203     T_case = read();
204     while(T_case--){
205         tank = read(); st = read(); ed = read();
206         Dijkstra(st);
207     }
208     return 0;
209 }

View Code