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 4Sample Output
170
impossibleSource
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升的最小花费。那么，经过每一站时候，如果到下一站加油可能最优，那么就加。参考了题解：传送门。
每次只加一单位的汽油，如果能够到达下一个节点就进行更新，如果不能到达就继续加油，使用优先队列维护，满足当前的消费为最低消费。其实就相当把一个点拆成一百个点（因为容量最多为100），把拆出来的点理解为一个状态，理解为求解不同状态之间的最短路。
代码
| Status | Accepted |
|---|---|
| Time | 130ms |
| Length | 2470 |
#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;
}打组队赛的时候在小白书上找到了原题，但是没有题解而且之前没有做过，实在是太难受了，更可惜的是，即使知道是最短路的题也不会写，完全不会图上的dp。
The end.
2018-08-18 星期六