TOI14: Logistics

#include <bits/stdc++.h>

using namespace std;
const int N = 1e2 + 10;
const int F = 1e2 + 10;
const int inf = 1e9;
using pii = pair <int, int>;
using ppiipii = pair <pii, pii>;
vector <pii> g[N];
int dis[N][F][2], price[N];
bool vs[N][F][2];

int main(){

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

    for(int i=1;i<=n;i++) scanf("%d", &price[i]);

    int st, ed, maxf; scanf("%d %d %d", &st, &ed, &maxf);

    int m; scanf("%d", &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});
        g[v].push_back({u, w});
    }

    for(int u=0;u<=n;u++){
        for(int f=0;f<=maxf;f++){
            dis[u][f][0] = dis[u][f][1] = inf;
        }
    }

    priority_queue <ppiipii, vector <ppiipii>, greater <ppiipii>> pq;
    dis[st][0][0] = 0;
    pq.push({ {0, st} , {0, 0} });
    while(!pq.empty()){
        int d = pq.top().first.first;
        int u = pq.top().first.second;
        int f = pq.top().second.first;
        int use = pq.top().second.second;
        pq.pop();
        if(vs[u][f][use]) continue;
        vs[u][f][use] = true;
        if(u == ed and f == maxf){
            printf("%d", d);
            return 0;
        }
        for(auto vw: g[u]){
            int v = vw.first;
            int w = vw.second;
            if(f >= w and !vs[v][f - w][use] and d < dis[v][f - w][use]){
                dis[v][f - w][use] = d;
                pq.push({ {dis[v][f - w][use], v} , {f - w, use} });
            }
        }
        if(f + 1 <= maxf and !vs[u][f + 1][use] and d + price[u] < dis[u][f + 1][use]){
            dis[u][f + 1][use] = d + price[u];
            pq.push({ {dis[u][f + 1][use], u} , {f + 1, use} });
        }
        if(!use and f < maxf and !vs[u][maxf][1] and d < dis[u][maxf][1]){
            dis[u][maxf][1] = d;
            pq.push({ {dis[u][maxf][1], u} , {maxf, 1} });
        }
    }

    return 0;
}