SMMR-176: Trip Planner

#include <bits/stdc++.h>

using namespace std;
using pi = pair <int, int>;
using pii = pair <int, pi>;
const int N = 1e3;
const int C = 1e2;
const int INF = 2e9;
vector <pi> g[N+10];
int p[N+10];
bool visited[N+10][C+10];
int dis[N+10][C+10];
int mn = INF;

int f(int c, int s, int e){

    if(c < mn) return -1;

    priority_queue <pii, vector <pii>, greater <pii>> pq;
    dis[s][c] = 0;
    pq.push({0, {s, 0}});

    while(!pq.empty()){
        int d = pq.top().first;
        int u = pq.top().second.first;
        int oil = pq.top().second.second;
        pq.pop();
        if(visited[u][oil])
            continue;
        visited[u][oil] = true;
        if(u == e){
            return d;
        }
        for(auto vw: g[u]){
            int v = vw.first;
            int w = vw.second;
            if(oil >= w and !visited[v][oil-w] and d < dis[v][oil-w]){
                dis[v][oil-w] = d;
                pq.push({dis[v][oil-w], {v, oil-w} });
            }
            if(oil + 1 <= c and oil + 1 >= w and !visited[v][oil+1-w] and d + p[u] < dis[v][oil+1-w]){
                dis[v][oil+1-w] = d + p[u];
                pq.push({dis[v][oil+1-w] , {v, oil+1-w}});
            }
        }
        if(oil + 1 <= c) pq.push({d+p[u], {u, oil+1}});
    }

    return -1;
}

int main(){

    int n, m;
    scanf("%d%d", &n, &m);

    for(int i=0;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);
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        mn = min(mn, w);
    }

    int q;
    scanf("%d", &q);

    while(q--){
        int c, s, e;
        scanf("%d%d%d", &c, &s, &e);

        for(int i=0;i<=n;i++){
            for(int j=0;j<=c;j++){
                visited[i][j] = false;
                dis[i][j] = INF;
            }
        }

        int ans = f(c, s, e);
        if(ans == -1) printf("impossible");
        else printf("%d", ans);
        printf("\n");

    }

    return 0;
}
/*
ไม่ควรเติมน้ำมันทุกแบบ
ควร ค่อยๆเติมแล้วดูว่าเดินได้มั้ย
*/