传送门

把每个点拆成100个点，分别表示到这个点的时候油量剩余的状态。跑最短路即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int p[maxn], val[maxn], e[maxn], pre[maxn], h[maxn], cnt;
void add(int u, int v, int w)
{
    e[cnt] = v; val[cnt] = w; pre[cnt] = h[u]; h[u] = cnt++;
}
struct Ver{
    int a, b, c;
    bool operator<(const Ver &W)const 
    {
        return c > W.c;
    }
};
int dis[1010][110];
bool vis[1010][110];
int dijkstra(int cost, int start, int end)
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis,0, sizeof vis);
    priority_queue<Ver> pq;
    pq.push({start, 0, 0});
    dis[start][0] = 0;
    while(pq.size())
    {
        Ver t = pq.top(); pq.pop();
        if(t.a == end) return t.c;
        if(vis[t.a][t.b]) continue;
        vis[t.a][t.b] = 1;
        if(t.b < cost)
        {
            if(dis[t.a][t.b + 1] > t.c + p[t.a])
            {
                dis[t.a][t.b + 1] = t.c + p[t.a];
                pq.push({t.a, t.b + 1, t.c + p[t.a]});
            }
        }
        for(int i = h[t.a]; ~i; i = pre[i])
        {
            int y = e[i];
            if(t.b - val[i] >= 0)
            {
                if(dis[y][t.b - val[i]] > t.c)
                {
                    dis[y][t.b - val[i]] = t.c;
                    pq.push({y, t.b - val[i], t.c});
                }
            }
        }
    }
    return -1;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i++) scanf("%d", &p[i]);
    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        u++, v++;
        add(u, v, w); add(v, u, w);
    } 
    int T; scanf("%d", &T);
    while(T--)
    {
        int C, start, end;
        scanf("%d%d%d", &C, &start, &end);
        start++, end++;
        int ans = dijkstra(C, start, end);
        if(~ans) cout << ans << endl;
        else cout << "impossible" << endl;
    }
}