TOI15: Cave

#include <bits/stdc++.h>

using namespace std;
using pi = pair <int, int>;
using pii = pair <int, pi>;
const int INF = 2e9;
const int N = 2e3 + 10;
const int T = 1e9;
vector <pi> g[N], node, cdis;
int dis[N][N];
bool vs[N][N];
int n, st, ed, m;

int main(){

    scanf("%d%d%d%d", &n, &st, &ed, &m);

    for(int i=1;i<=m;i++){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w});
    }

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

    /// dis[v][count edge]
    priority_queue <pii, vector<pii>, greater<pii>> pq;
    dis[st][0] = 0;
    pq.push({dis[st][0], {st, 0}});
    while(!pq.empty()){
        int d = pq.top().first;
        int u = pq.top().second.first;
        int e = pq.top().second.second;
        pq.pop();
        if(vs[u][e]) continue;
        vs[u][e] = true;
        if(e + 1 == n) continue;
        for(auto vw: g[u]){
            int v = vw.first;
            int w = vw.second;
            if(!vs[v][e + 1] and d + w < dis[v][e + 1]){
                dis[v][e + 1] = d + w;
                pq.push({dis[v][e + 1], {v, e + 1}});
            }
        }
    }

    /// cdis[u] = {dis, e};
    int bf = INF;
    for(int e=1;e<=n-1;e++){
        if(dis[ed][e] <= T and dis[ed][e] < bf){
            cdis.push_back({dis[ed][e], e});
            bf = dis[ed][e];
        }
    }

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

    for(int i=0;i<L;i++){
        int h;
        scanf("%d", &h);
        int mn = INF;
        for(auto we: cdis){
            int w = we.first;
            int e = we.second;
            mn = min(mn, w + (e - 1) * h);
        }
        printf("%d ", mn);
    }

    return 0;
}

/*
    state graph: dis(u, จำนวน edge) = ระยะทางที่น้อยที่สุดจาก st ไป u ใด ๆ
    Query: dis(ed, จำนวน edge) + (จำนวน edge - 1) * hi
*/