gistfile1.cpp

#define MAXC 1010
#define MAXX 110
#define INF 2000000000
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

int n, m, s, d, qr, c;
int P[MAXC];
int G[MAXC][MAXC];

int map[MAXC][MAXX];
int revMap[MAXC*MAXX];

struct Node {
    int w, f;
    Node(int w, int f) : w(w), f(f){}
};

struct Edge {
    int t, c, k;
    Edge(int t, int c, int k) : t(t), c(c), k(k){}
    const inline bool operator < (const Edge& e) const {
        return this->c > e.c;
    }
};

vector<vector<Edge> > V;

int main() {
    cin >> n >> m;
    for(int i=0; i<n; i++) {
        cin >> P[i];
    }

    for(int i=0; i<m; i++) {
        cin >> s >> d;
        cin >> G[s][d];
        G[d][s] = G[s][d];
    }


    V.clear(); V.push_back(vector<Edge>());
    memset(map, 0, sizeof(map));
    memset(revMap, 0, sizeof(revMap));

    queue<Node> q;
    q.push(Node(s, 0));

    map[s][0] = V.size();
    V.push_back(vector<Edge>());

    //cria o grafão
    while(!q.empty()) {
        Node e = q.front(); q.pop();
        //cout << "> " <<  e.w << " " << e.f << endl;
        for(int i=0; i<n; i++) {
            if (G[e.w][i] > 0 && G[e.w][i] <= e.f) {
                int nw = i;
                int nf = e.f - G[e.w][i];
                int nidx = map[nw][nf];

                //cout << e.w << " " << e.f << " - " << nw << " " << nf << endl;

                if (nidx == 0) {
                    nidx = V.size();
                    map[nw][nf] = nidx;
                    revMap[nidx] = nw;
                    V.push_back(vector<Edge>());
                    q.push(Node(nw, nf));
                }

                V[map[e.w][e.f]].push_back(Edge(nidx, 0, 0));
            }
        }

        if (e.f < MAXX) {
            int nidx = map[e.w][e.f+1];

            //cout << e.w << " " << e.f << " - " << e.w << " " << e.f+1 << endl;

            if (nidx == 0) {
                nidx = V.size();;
                map[e.w][e.f+1] = nidx;
                revMap[nidx] = e.w;
                V.push_back(vector<Edge>());
                q.push(Node(e.w, e.f+1));
            }

            V[map[e.w][e.f]].push_back(Edge(nidx, P[e.w], e.f+1));
        }
    }
    //até aqui cria o grafo


    cin >> qr;

    for(int ii=0; ii<qr; ii++) {
        //para cada query
        cin >> c >> s >> d;

        //então, dijkstra
        int nn = V.size();
        int y[nn];
        priority_queue<Edge> heap;

        for(int i=0; i<nn; i++)
            y[i] = (i!=map[s][0]?INF:0);

        heap.push(Edge(map[s][0], 0, 0));

        while(!heap.empty()) {
            Edge e = heap.top(); heap.pop();

            if (e.c > y[e.t]) continue;

            for(int i=0; i<V[e.t].size(); i++) {
                if (V[e.t][i].k > c) continue;

                int aux = y[e.t] + V[e.t][i].c;
                int nxt = V[e.t][i].t;
                //cout << aux << endl;
                if (aux < y[nxt]) {
                    y[nxt] = aux;
                    heap.push(Edge(nxt, aux, V[e.t][i].k));
                }
            }
        }

        int minn = INF;
        //cout << d << endl;
        for(int i=0; i<=c; i++) {
            //cout << y[map[d][i]] << " ";
            minn = min(y[map[d][i]], minn);
        }
        //cout << endl;
        if (minn < INF)
            cout << minn << endl;
        else
            cout << "impossible" << endl;
    }




}