题目描述

有 $N$ 个城市（编号 $0, 1 \cdots N-1$）和 $M$ 条道路，构成一张无向图。

在每个城市里边都有一个加油站，不同的加油站的单位油价不一样。

现在你需要回答不超过 $100$ 个问题，在每个问题中，请计算出一架油箱容量为 $C$ 的车子，从起点城市 $S$ 开到终点城市 $E$ 至少要花多少油钱？

注意： 假定车子初始时油箱是空的。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数，代表 $N$ 个城市的单位油价，第 $i$ 个数即为第 $i$ 个城市的油价 $p _ i$。

接下来 $M$ 行，每行包括三个整数 $u,v,d$，表示城市 $u$ 与城市 $v$ 之间存在道路，且车子从 $u$ 到 $v$ 需要消耗的油量为 $d$。

接下来一行包含一个整数 $q$，代表问题数量。

接下来 $q$ 行，每行包含三个整数 $C$、$S$、$E$，分别表示车子油箱容量、起点城市 $S$、终点城市 $E$。

输出格式

对于每个问题，输出一个整数，表示所需的最少油钱。

如果无法从起点城市开到终点城市，则输出impossible。

每个结果占一行。

数据范围

$1 \leq N \leq 1000$,
$1 \leq M \leq 10000$,
$1 \leq p _ i \leq 100$,
$1 \leq d \leq 100$,
$1 \leq C \leq 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

算法

(dijkstra) $O(q(n + m) \log n)$

首先不难看出这题是一道最短路问题。
但是这个求最短路还涉及到了当前车上的油量，这个状态是我们需要记录下来的。

求最短路中在每个点上记录多个元素，有个很常用的技巧，就是拆点。
我们可以将第 $i$ 个点拆成 $p _ i$ 个点，每个点有两个属性 $(编号, 当前剩余的油量)$。
我们一共有最多有 $1000$ 个点，到每个点剩的油量最大是 $100$，所以我们最多拆出 $10 ^ 5$ 个点，可以接受。

那么原问题就转化成了在一个最多有$10 ^ 5$个点，$10 ^ 4$条无向边的图上，求出从 $(S, 0)$ 到 $(T, 0)$ 的最短路
在求最短路中，我们有两种选择方案：（设该点为u到该点所剩油量为c，油箱容量为C）

• 如果 $c + 1 \leq C$，说明油箱至少还能加一升油，那么我们可以在该点加一升油，然后更新加一升油的状态$(u, c + 1)$
• 如果对于从该点出发的某条边edge，走该边的花费$edge.cost \leq c$，那么我们就可以从该边走过去，更新到达下一个点的状态$(edge.to, c - edge.cost)$

我们只需要在做 dijkstra 的时候，分别处理这两种情况即可，详见代码及注释。

时间复杂度

dijkstra的时间复杂度是 $\mathcal O((n + m) \log n)$
一共做 $q$ 次，所以总的时间复杂度为 $\mathcal O(q(n + m) \log n)$

C++ 代码

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int C = 105;   // 最大油量
const int N = 1005;  // 点的数量
const int M = 20005; // 边的数量

struct Point     // 存每个点的状态
{
    int d, u, c; // d 存到这个点所花费的油钱，u 存点的编号，c 存当前还剩多少油
    bool operator < (const Point &t) const // 重载小于号。按大于好反过来重载小于号，后面在建堆的时候建大根堆就可以了
    {
        return d > t.d;
    }
};
int n, m;
int p[N], dist[N][C]; // p 存每个点上的油价，dist 存到每个被拆的点的最低油钱
int h[N], w[M], e[M], ne[M], idx; // 存图
bool st[N][C];        // 用于 dijkstra 中记录每个点是否已经出队

void add(int a, int b, int c) // 加边函数
{
    e[ ++ idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
}

// 求出从 start 到 end，油箱容量为 c 的最短距离。若不能到，返回 -1
inline int dijkstra(int c,int start,int end)
{
    priority_queue<Point> heap;      // 由于按大于号重载了小于号，所以建大根堆即可
    memset(dist, 0x3f, sizeof dist); // 将到所有点的油钱都初始化为正无穷
    memset(st, false, sizeof st);    // 将 st 初始化为 false
    heap.push((Point){0, start, 0}); // 将 start 加入堆中
    dist[start][0] = 0;              // 到该点的油钱初始化为 0
    while (heap.size())
    {
        Point t = heap.top();       // 取出堆顶元素
        heap.pop();
        if (t.u == end) return t.d; // 如果到了 end，返回到 end 的距离
        if (st[t.u][t.c]) continue; // 如果该点已经出队过，则跳过
        st[t.u][t.c] = true;        // 记录该点已经出队过
        if (t.c < c)                // 如果 t.c + 1 <= 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((Point){dist[t.u][t.c + 1], t.u, t.c + 1}); // 该点加入堆中
            }
        for (int i = h[t.u]; i; i = ne[i]) // 遍历该点所有能到达的点
            if (t.c >= w[i])               // 如果用当前所剩的油量能到该点
                if (dist[e[i]][t.c - w[i]] > t.d) // 如果这次到该点的油钱小于原来的
                {
                    dist[e[i]][t.c - w[i]] = t.d; // 那么更新原来的
                    heap.push((Point){t.d, e[i], t.c - w[i]}); // 将该点加入堆中
                }
    }
    return -1; // 如果到不了 end，返回 -1
}

int main()
{
    scanf("%d%d", &n, &m);  // 读入点数和边数
    for (int i = 0; i < n; i ++ )
        scanf("%d", &p[i]); // 读入每个点的油价

    while (m -- )           // 读入 m 条边并建图
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c); // 无向边
    }

    int T;
    scanf("%d", &T);        // 读入问题数量
    while (T -- )           // 处理每个问题
    {
        int C, S, E;
        scanf("%d%d%d", &C, &S, &E);
        int d = dijkstra(C, S, E);
        if (d == -1) puts("impossible");
        else    printf("%d\n", d);
    }

    return 0;
}