TOI14: Logistics

#include <bits/stdc++.h>
using namespace std;

typedef tuple<int, int, int, int> tiiii;
typedef pair<int, int> pii;

const int N = 100;

vector<pii> adj[N + 10];
int fuelCost[N + 10];
int nVertex, nEdge, mxFuel, st, ed;

int main(){

    scanf("%d", &nVertex);
    for(int i = 1; i <= nVertex; ++i){
        scanf("%d", &fuelCost[i]);
    }
    scanf("%d %d %d %d", &st, &ed, &mxFuel, &nEdge);
    for(int i = 1; i <= nEdge; ++i){
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    priority_queue<tiiii, vector<tiiii>, greater<tiiii>> priQ; // {cost, u, fuel, free}
    vector<vector<vector<int>>> cost(nVertex + 1, vector<vector<int>>(mxFuel + 1, vector<int>(2, 1e9)));
    vector<vector<vector<bool>>> visited(nVertex + 1, vector<vector<bool>>(mxFuel + 1, vector<bool>(2, false)));
    cost[st][0][1] = 0;
    priQ.emplace(0, st, 0, 1);
    while(!priQ.empty()){
        int u = get<1>(priQ.top());
        int fuel = get<2>(priQ.top());
        int free = get<3>(priQ.top());
        priQ.pop();
        if(visited[u][fuel][free]){
            continue;
        }
        visited[u][fuel][free] = true;
        if(u == ed && fuel == mxFuel){
            cout << cost[ed][mxFuel][free];
            break;
        }
        for(int i = fuel + 1; i <= mxFuel; ++i){
            if(free == 1 && !visited[u][i][0] && cost[u][fuel][1] < cost[u][i][0]){
                cost[u][i][0] = cost[u][fuel][1];
                priQ.emplace(cost[u][i][0], u, i, 0);
            }
            if(!visited[u][i][free] && cost[u][fuel][free] + (i - fuel) * fuelCost[u] < cost[u][i][free]){
                cost[u][i][free] = cost[u][fuel][free] + (i - fuel) * fuelCost[u];
                priQ.emplace(cost[u][i][free], u, i, free);
            }
        }
        for(pii nxt : adj[u]){
            int v = nxt.first;
            int w = nxt.second;
            if(fuel >= w && !visited[v][fuel - w][free] && cost[u][fuel][free] < cost[v][fuel - w][free]){
                cost[v][fuel - w][free] = cost[u][fuel][free];
                priQ.emplace(cost[v][fuel - w][free], v, fuel - w, free);
            }
        }
    }

    return 0;
}