【POJ No. 3635】 加满油箱 Full Tank?

【POJ No. 3635】 加满油箱 Full Tank?

POJ题目地址

【题意】

城市之间的油价是不一样的，编写程序，寻找最便宜的城市间旅行方式。

在旅行途中可以加满油箱。假设汽车每单位距离使用一单位燃料，从一个空油箱开始。

【输入输出】

输入：

输入的第1行包含n （1≤n ≤1000）和m （0≤m ≤10000），表示城市和道路的数量。下一行包含n 个整数pi （1≤pi≤100），其中pi 表示第i 个城市的燃油价格。接下来的m 行，每行都包含3个整数u 、v （0≤u , v

输出：

对于每个查询，都输出给定容量的汽车从s 到e 的最便宜旅程的价格，如果无法从s 到e ，则输出“impossible”。

【样例】

【思路分析】

这道题属于加油站加油问题。

给定n 个节点、m 条边，每走1单位的路径都会花费1单位的油量，并且不同的加油站价格是不同的。现在有一些询问，每一个询问都包括起点、终点及油箱的容量，求从起点到达终点所需的最少花费。可以采用优先队列分支限界法搜索。

涉及两个维度的图最短路径，一个是费用，一个是地点。可以把当前节点对应的油量抽象成多个节点（例如在位置0有1升油是一个节点，在位置0有2升油是一个节点），把费用看作边，那么最少费用就可以类似Dijsktra算法那样不断地加入节点。于是得到一个扩展节点的策略：每次都加1升油；如果依靠加的油足够走到下一个节点，就走到下一个节点（减去路上消耗的油，花费不变）；在广度优先搜索中将所有可扩展的节点都加入优先队列中，如果到达终点，则返回花费。

【算法设计】

① 定义一个优先队列，将起点及当前油量、花费作为一个节点(st,0,0)入队。

② 如果队列不空，则队头(u ,vol,cost)出队，并标记该节点油量已扩展，vis[u ][vol]=1。

③ 如果u 正好是目标ed，则返回花费cost。

④ 如果当前油量小于油箱容量，且u 的油量vol+1未扩展，则将该节点(u ,vol+1, cost+price[u ])入队。

⑤ 检查u 所有邻接点v ，如果当前油量大于或等于边权w ，且v节点的油量vol-w 未扩展，则将该节点(v ,vol-w ,cost)入队。

⑥ 转向步骤2。

【算法优化】

用一个数组dp[i ][j ]表示在节点i 、当前油量为j 时的最小花费。在当前节点及油量对应的花费更小时才生成节点，生成的节点会少很多，但由于系统数据量不大，运行时间差不多。

采用优化后的算法生成节点的过程如下图所示。

【算法实现】(加上 动规 优化)

#include
#include
#include
#include

using namespace std;

const int maxn = 1010;
const int maxm = 20010;

struct edge{
	
	int v, w ,next;
}edge[maxm];

struct node{
	int u , vol , cost;
	
	node(int u_ , int vol_ , int cost_){
		
		u = u_;
		vol = vol_;
		cost = cost_;
	}
	bool operator < (const node &a) const{
		
		return cost > a.cost;
	}
};

int head[maxn];
bool vis[maxn][105];
int dp[maxn][105]; //dp[i][j] 表示在顶点i，当前油量为j 时的最小花费
int n , m , V , st, ed , cnt , price[maxn];

void add(int u  ,int v , int w){
	
	edge[cnt].v = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt ++;
} 

int bfs(){
	
	memset(vis,  0 , sizeof(vis));
	memset(dp , 0x3f, sizeof(dp));
	
	priority_queue<node>Q;
	
	Q.push(node(st , 0 , 0));
	dp[st][0] = 0;
	
	while(!Q.empty()){
		
		node cur = Q.top();
		Q.pop();
		
		int u = cur.u,  vol = cur.vol , cost = cur.cost;
		vis[u][vol] = 1;
		
		if(u == ed){
			
			return cost;
		}
		if(vol < V && !vis[u][vol + 1] && dp[u][vol] + price[u] < dp[u][vol + 1]){
			dp[u][vol + 1] = dp[u][vol] + price[u];
			Q.push(node(u , vol + 1, cost + price[u]));
		}
		
		for(int i = head[u]; ~i ; i = edge[i].next){
			
			int  v = edge[i].v , w = edge[i].w;
			if(vol >= w && !vis[v][vol - w] && cost < dp[v][vol - w]){
				dp[v][vol - w] = cost;
				Q.push(node(v , vol - w, cost));
			}
		}
	}
	return -1;
}

int main(){
	
	int u , v, w;
	while(~scanf("%d%d" , &n , &m)){
		
		for(int i = 0 ; i < n ; i++){
			
			scanf("%d" , &price[i]);
		}
		cnt = 0;
		memset(head , -1 , sizeof(head));
		
		while(m --){
			
			scanf("%d%d%d" , &u , &v, &w);
			add(u , v , w);
			add(v , u , w);
		}
		
		int q;
		scanf("%d" , &q);
		while(q --){
			
			scanf("%d%d%d" , &V , &st, &ed);
			int ans = bfs();
			
			if(ans == -1){
				puts("impossible");
			}
			else{
				printf("%d\n" , ans);
			}
		}
	}
	
	return 0;
}


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
115
116
117
118
119
120
121