# UVA11367 Full Tank? （最短路+dp）

## Full Tank?

### 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<=pi<=100, where pi 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

2007 Nordic Collegiate Programming Contest

### 链接

https://cn.vjudge.net/problem/UVA-11367

### 题意

n个城市有m条道路。每个城市的油价不一样，给出起点s和终点t，以及汽车的油箱的容量，求从城市s到城市t 的最便宜路径。（一开始油箱是空的，你每次可以选择加多少升。假设每单位的距离消耗1L汽油）

### 题解

dijkstra的变形。用优先队列来维护当前花费的最小值。设dp[i][j]为到达城市i的消耗剩余汽油为j升的最小花费。那么，经过每一站时候，如果到下一站加油可能最优，那么就加。

### 代码

StatusAccepted
Time130ms
Length2470
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1010;
const int maxm = 10010;
int n, m, c;
int head[maxn], tot;
int dist[maxn][maxn]; // 到达第i点剩余油量为j的最小花费
int a[maxn];

struct Edge
{
int to, cost, next;
}edge[maxm<<2];

struct Node
{
int idx, cost, cap;
Node(){}
Node(int _idx, int _cost, int _cap): idx(_idx), cost(_cost), cap(_cap){}
bool operator < (const Node & r) const
{
return cost > r.cost;
}
};

void init()
{
memset(head, -1, sizeof(head));
tot = 0;
}

void addedge(int u, int v, int w)
{
edge[tot].to = v;
edge[tot].cost = w;
edge[tot].next = head[u];
head[u] = tot++;
}

int dijkstra(int s, int t)
{
priority_queue <Node> Q;
for (int i = 0; i <= n; ++i)
for (int j = 0; j < 110; ++j) // 最多为100
dist[i][j] = inf;
while (!Q.empty())
Q.pop();
Q.push(Node(s, 0, 0)); // 从s开始，花费为0，剩余油量为0
while (!Q.empty())
{
Node u = Q.top();
Q.pop();
int idx = u.idx, cost = u.cost, cap = u.cap;
if (idx == t) // 到达t点，返回最小花费
return u.cost;
// 在容量范围之内且比之前状态的花费大，更新
if (cap < c && dist[idx][cap + 1] > cost + a[idx]) // 加油，每次加1L
{
dist[idx][cap + 1] = cost + a[idx];
Q.push(Node(idx, dist[idx][cap + 1], cap + 1));
}
for (int i = head[idx]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (cap < edge[i].cost) // 当前油量不够到达下一点
continue;
if (dist[v][cap-edge[i].cost] > cost) // 到下一点的花费少于可以比记录的更少就更新
{
dist[v][cap-edge[i].cost] = cost;
Q.push(Node(v, cost, cap-edge[i].cost));
}
}
}
return -1;
}

int main()
{
int s, t, u, v, w, q;
while (scanf("%d%d", &n, &m) != EOF)
{
init();
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
u++, v++; // 下标
addedge(u, v, w);
addedge(v, u, w);
}
scanf("%d", &q);
while (q--)
{
scanf("%d%d%d", &c, &s, &t);
s++, t++; // 下标
int ans = dijkstra(s, t);
if (ans == -1)
printf("impossible\n");
else
printf("%d\n", ans);
}
}
return 0;
}

The end.
2018-08-18 星期六