Trip Planner

#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;

typedef long long int ll;

ll min(ll a,ll b){
    return (a < b ? a : b);
}

struct edge{
    int v;
    ll w;
};

struct elem{
    int u;
    ll
     fuel;
    ll dis;
    bool operator < (const elem& rhs)const
    {
        return dis > rhs.dis;
    }
};

int const N = 1010;

vector<edge> adj[N];

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    ll price[n];
    for(int i = 0 ; i < n ; i ++){
        scanf("%lld",&price[i]);
    }
    for(int i = 0 ; i < m ; i ++){
        int u,v;
        ll w;
        scanf("%d %d %lld",&u,&v,&w);
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    ll dist[n][110];
    bool visited[n][110];
        for(int i = 0 ; i < n ; i ++)for(int j = 0 ; j < 110 ; j ++){
            dist[i][j] = 1e18;
            visited[i][j] = false;
        }

    int T;
    scanf("%d",&T);
    for(int t = 0 ; t < T ; t ++){
        int c,b,e;
        scanf("%d %d %d",&c,&b,&e);
        for(int i = 0 ; i < n ; i ++){
            for(int j = 0 ; j < 110 ; j ++){
                dist[i][j] = 1e18;
                visited[i][j] = false;
            }
        }
        priority_queue<elem> pq;
        dist[b][0] = 0;
        pq.push({b,0,dist[b][0]});
        bool check = true;
        while(!pq.empty()){
            int u = pq.top().u;
            ll fuel = pq.top().fuel;
            ll dis = pq.top().dis;
            pq.pop();
            if(visited[u][fuel])continue;
            visited[u][fuel] = true;
            if(u == e){
                printf("%lld\n",dis);
                check = false;
                break;
            }
            if(fuel+1 <= c){
                if(!visited[u][fuel+1] && dist[u][fuel] + price[u] < dist[u][fuel+1]){
                    dist[u][fuel+1] = dist[u][fuel] + price[u];
                    pq.push({u,fuel+1,dist[u][fuel+1]});
                }
            }
            for(int i = 0 ; i < adj[u].size() ; i ++){
                int v = adj[u][i].v;
                ll w = adj[u][i].w;
                if(fuel <= c){
                    if (fuel < w) continue;
                    if(!visited[v][fuel-w] && dist[u][fuel] < dist[v][fuel-w]){
                        dist[v][fuel-w] = dist[u][fuel];
                        pq.push({v,fuel-w,dist[v][fuel-w]});
                    }
                }
            }
        }
        while(!pq.empty())pq.pop();
        if(check){
            printf("impossible\n");
        }
    }
    return 0;
}