LOGISTICS

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

typedef long long int ll;

struct edge{
    int v;
    ll w;
};

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

int main()
{
    int n;
    scanf("%d",&n);
    ll cost[n+1];
    for(int i = 1 ; i <= n ; i ++){
        scanf("%lld",&cost[i]);
    }
    int b,e,c;
    scanf("%d %d %d",&b,&e,&c);
    int m;
    scanf("%d",&m);

    vector<edge> adj[n+1];
    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});
    }

    bool visited[2][n+1][c+1];for(int k = 0 ; k < 2 ; k ++)for(int i = 0 ; i <= n ; i ++)for(int j = 0 ; j <= c ; j ++)visited[k][i][j] = false;

    priority_queue<elem> pq;
    pq.push({1,b,0,0});
    while(!pq.empty()){
        int u = pq.top().u;
        ll fuel = pq.top().fuel;
        ll dis = pq.top().dis;
        int vc = pq.top().vc;
        pq.pop();
        if(visited[vc][u][fuel])continue;
        visited[vc][u][fuel] = true;
    //  printf("test (%d,%d,%lld) : %lld\n",vc,u,fuel,dis);
        if(u == e && fuel == c){
            printf("%lld",dis);
            return 0;
        }
        if(vc == 1/* && fuel < c*/){
            pq.push({0,u,c,dis});
        }
        if(fuel+1 <= c){
            pq.push({vc,u,fuel+1,dis+cost[u]});
        }

        for(int i = 0 ; i < adj[u].size() ; i ++){
            int v = adj[u][i].v;
            ll w = adj[u][i].w;

            if(fuel >= w){
                ll nfuel = fuel - w;
                if(!visited[vc][v][nfuel]){
                    pq.push({vc,v,nfuel,dis});
                }

            }
        }
    }
    printf("error -1\n");
    return -1;
}