原题链接：https://www.acwing.com/problem/content/178/

题目描述

有N个城市（编号0、1…N-1）和M条道路，构成一张无向图。 在每个城市里边都有一个加油站，不同的加油站的单位油价不一样。 现在你需要回答不超过100个问题，在每个问题中，请计算出一架油箱容量为C的车子，从起点城市S开到终点城市E至少要花多少油钱？ 注意： 假定车子初始时油箱是空的。 输入格式 第一行包含两个整数N和M。 第二行包含N个整数，代表N个城市的单位油价，第i个数即为第i个城市的油价pi。 接下来M行，每行包括三个整数u,v,d，表示城市u与城市v之间存在道路，且车子从u到v需要消耗的油量为d。 接下来一行包含一个整数q，代表问题数量。 接下来q行，每行包含三个整数C、S、E，分别表示车子油箱容量、起点城市S、终点城市E。 输出格式 对于每个问题，输出一个整数，表示所需的最少油钱。 如果无法从起点城市开到终点城市，则输出”impossible”。 每个结果占一行。 数据范围 1≤N≤1000, 1≤M≤10000, 1≤pi≤100, 1≤d≤100, 1≤C≤100 输入样例： 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 输出样例： 170 impossible

题解

从起点到终点的最小花费，可以转化为最短路问题。但是这里有一个限制条件，就是当前剩余油量要大于从某一个点到另一个点的花费。那么这条边就是成立的并且它的权重我们可以看成是0，即不需要加油就可以走到另一个点。 那加油这个操作怎么转化成一条边呢？可以用一个常用技巧------拆点。这里的解决办法是：将点的第几个点和剩余油量封装成一个点（ver, cap) 。 两条边： 将加一升油看成从点（ver, cap）–>(ver, cap + 1){cap + 1< C(总容量) } 边权 = price[ver] 将从一个点走到另一个点表示为(ver, cap)—>(newVer, cap - cost[i]){cap >= cost[i]}边权 = 0

#include <iostream> #include <cstring> #include <queue> #include <algorithm> using namespace std; const int N = 1010, M = 20010, C = 110; int dist[N][C]; bool st[N][C]; int p[N]; int h[N], e[M], ne[M], w[M],idx; int n , m; struct Ver { int d, u , c; bool operator <(const Ver& W) const { return d > W.d; } }; void add(int a, int b, int c) { e[idx] = b; w[idx] = c, ne[idx] = h[a]; h[a] = idx++; } int dijkstra(int c, int start, int end) { priority_queue<Ver> heap; memset(st, false, sizeof st); memset(dist, 0x3f, sizeof dist); heap.push({0, start, 0}); dist[start][0] = 0; while(heap.size()) { auto t = heap.top(); heap.pop(); if(t.u == end) return t.d; if(st[t.u][t.c]) continue; st[t.u][t.c] = true; if(t.c < c) { if(dist[t.u][t.c + 1] > t.d + p[t.u]) { dist[t.u][t.c + 1] = t.d + p[t.u]; heap.push({dist[t.u][t.c + 1], t.u, t.c + 1}); } } for(int i = h[t.u]; ~i; i = ne[i]) { int j = e[i]; if(t.c >= w[i]) { if(dist[j][t.c - w[i]] > t.d) { dist[j][t.c - w[i]] = t.d; heap.push({dist[j][t.c - w[i]], j, t.c - w[i]}); } } } } return -1; } int main() { cin >> n >> m; for(int i = 0; i < n; i++) cin >> p[i]; memset(h, -1, sizeof h); while(m--) { int a, b, c; cin >> a >> b >> c; add(a, b, c); add(b, a, c); } int query; scanf("%d", &query); while(query--) { int c, s, e; scanf("%d%d%d", &c, &s, &e); int t = dijkstra(c, s, e); if(t == -1) puts("impossible"); else cout << t << endl; } return 0; }