The following problem is solved by branch and bound method and the C++ code is given Li wants to travel around the country by car. He finds that the price of gasoline varies from city to city during the trip. It is obvious that if he can adopt a reasonable way to fill up, he will save the cost of the whole trip. Assuming the car starts with an empty tank, it will use one unit of gas for every unit of distance it travels. Please help Xiao Li find the most economical way to complete his entire road trip. Input requirements: The first line of the input contains two integers n (1 ≤ n ≤ 1000) and m (0 ≤ m ≤ 10000), which represent the number of cities and the number of roads, respectively. The following line contains n integers, each representing the price of gasoline in n cities. The following m lines, each containing three integers u,v,d, represent the city u, and the distance between v is d (1 ≤ d ≤ 100). The last line contains three integers c (1 ≤ c ≤ 100),s, and e, which represent the capacity of the tank, the city of departure, and the city of last arrival, respectively. Output requirements: If it is possible to help Xiao Li find a route from s to e that is most economical, the corresponding cost will be output; otherwise, "impossible" will be output. Sample input: 5 5 10, 10, 20, 12, 13 0, 1, 9 0, 2, 8 One, two, one 1, 3, 11 Two, three, seven Ten zero three Sample output: 170

以下是使用分支界限法解决该问题的C++代码：

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

using namespace std;

const int N = 1010, M = 20010;

int n, m, c, s, e;
int p[N], h[N], e[M], ne[M], w[M], idx;
int dist[N][110];  // dist[i][j]表示从起点到i，油量为j时的最短路
bool st[N][110];

struct Node
{
    int u, d, c;
    bool operator< (const Node& t) const
    {
        return d > t.d;
    }
};

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

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    priority_queue<Node> heap;
    heap.push({s, 0, 0});
    dist[s][0] = 0;
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int u = t.u, d = t.d, c = t.c;
        if (st[u][c]) continue;
        st[u][c] = true;
        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i], v = w[i];
            if (c + j <= c && dist[j][c + j] > dist[u][c] + p[j] * (c + j - d))
            {
                dist[j][c + j] = dist[u][c] + p[j] * (c + j - d);
                heap.push({j, dist[j][c + j], c + j});
            }
        }
    }

    int res = 0x3f3f3f3f;
    for (int i = 0; i <= c; i ++ ) res = min(res, dist[e][i]);
    if (res == 0x3f3f3f3f) return -1;
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &p[i]);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    scanf("%d%d%d", &c, &s, &e);

    int res = dijkstra();
    if (res == -1) puts("impossible");
    else printf("%d\n", res);

    return 0;
}

思路解析：

- 由于题目要求求最优解，因此我们可以想到使用单源最短路径算法来求解，这里我们采用Dijkstra算法。
- 由于油量对于最短路的计算有影响，因此我们可以使用二维数组`dist[i][j]`来表示从起点到i，油量为j时的最短路。
- 在Dijkstra算法中，每次从堆中取出距离起点最近的节点`u`，在遍历`u`的邻居节点`v`时，我们需要考虑两种情况：(1)当前油量`c`可以到达节点`v`，则直接更新`dist[v][c]`；(2)当前油量`c`无法到达节点`v`，则需要选择一个新的油量`c'`来到达节点`v`，那么节点`v`的油量将变为`c' - dis(u, v)`，因此我们可以将更新`dist[v][c']`的过程转化为更新`dist[v][c]`的过程，即`dist[v][c'] = dist[u][c] + p[v] * (c' - dis(u, v))`，其中`p[v]`表示节点`v`的油价。
- 由于油量是一个连续的值，因此我们需要使用bool数组`st[i][j]`来标记节点`i`的油量是否被访问过，防止重复访问。
- 最后，我们在`dist[e][i]`中取最小值即为答案。

时间复杂度：$O(mc\log n)$

其中，$m$为边数，$c$为油量，$n$为点数。