看到 shortest paths 来做的。
首先有一个贪心的策略，对于当前点 \(u\) 若不能直接往后走则肯定是选择经过的点中 \(w_i\) 最大的加。
很好理解，证明就不需要了。
所以可以定义状态 \(f_{u, mx}\) 为 \(u\) 点最大能加的值为 \(h_{mx}\) 的最优状态，\(h\) 是 \(w\) 离散化后的数组。
接下来考虑最优状态要在哪些位置上优：
首先因为答案跟次数有关，所以肯定次数 \(c\) 会是之一，其次，若 \(c\) 相同，则肯定是走完上一条边剩的金钱越多越好（注意走一条边剩下的金钱肯定小于上一个状态对应的 \(h'_{mx}\)，因为到了 \(u\) 后 \(h_{mx}
\ge h'_{mx}\)，则在前面选的更多肯定不优），所以剩下的金钱 \(s\) 也要算上。
综合一下，则要满足 \(c\) 最小的同时 \(s\) 最大。
大致证一下为什么这么选择：
- \(c = c', s > s'\)，这肯定选择 \((c, s)\)；
- \(c < c'\)，则因为 \(s, s' < h'_{mx} \ge h_{mx}\)，所以 \(s + (c' - c)\times h_{mx} > h'_{mx}\)，所以选择 \((c, s)\)。
然后发现这个 \((c, s)\) 的状态放在图上可以当做最短路来跑，直接跑就行。
时间复杂度 \(\mathcal{O}(T(nm\log_2 nm))\)。
// lhzawa(https://www.cnblogs.com/lhzawa/)
#include<bits/stdc++.h>
using namespace std;
const int N = 8e2 + 10;
const long long inf = 0x3f3f3f3f3f3f;
pair<long long, long long> dis[N][N];
bool vis[N][N];
vector<pair<int, long long> > ev[N];
long long w[N], wp[N];
int wh[N];
int main() {
int Tcs;
cin >> Tcs;
function<void ()> solve = []() -> void {
int n, m;
long long st;
scanf("%d%d%lld", &n, &m, &st);
function<void ()> clears = [n]() -> void {
for (int i = 1; i <= n; i++) {
ev[i].clear();
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
vis[i][j] = 0, dis[i][j] = {inf, inf};
}
}
return ;
};
clears();
for (int i = 1; i <= n; i++) {
scanf("%lld", &w[i]);
wp[i] = w[i];
}
sort(wp + 1, wp + n + 1);
for (int i = 1; i <= n; i++) {
wh[i] = lower_bound(wp + 1, wp + n + 1, w[i]) - wp;
}
function<void (int, int, long long)> add = [](int x, int y, long long z) -> void {
ev[x].push_back({y, z});
return ;
};
for (int i = 1; i <= m; i++) {
int x, y;
long long z;
scanf("%d%d%lld", &x, &y, &z);
add(x, y, z);
}
dis[1][wh[1]] = {0, st};
priority_queue<pair<pair<long long, long long>, pair<int, int> > > q;
q.push({{-0, st}, {1, wh[1]}});
for (; ! q.empty(); ) {
pair<pair<long long, long long>, pair<int, int> > tp = q.top();
q.pop();
int u = tp.second.first, mx = tp.second.second;
// printf("<- %d %d\n", u, mx);
if (vis[u][mx]) {
continue;
}
vis[u][mx] = 1;
// printf("%d %d %lld %lld\n", u, mx, dis[u][mx].first, dis[u][mx].second);
for (unsigned i = 0; i < ev[u].size(); i++) {
int v = ev[u][i].first;
long long y = ev[u][i].second;
long long c = max(0ll, y - dis[u][mx].second);
long long p = c / wp[mx] + (c % wp[mx] > 0);
pair<long long, long long> vdis = {dis[u][mx].first + p, dis[u][mx].second + p * wp[mx] - y};
if (vdis.first < dis[v][max(mx, wh[v])].first || (vdis.first == dis[v][max(mx, wh[v])].first && vdis.second > dis[v][max(mx, wh[v])].second)) {
// printf("-> %d %d %lld %lld\n", v, max(mx, wh[v]), vdis.first, vdis.second);
dis[v][max(mx, wh[v])] = vdis;
q.push({{-vdis.first, vdis.second}, {v, max(mx, wh[v])}});
}
}
}
long long ans = inf;
for (int i = 1; i <= n; i++) {
// printf("%d %lld %lld\n", i, dis[n][i].first, dis[n][i].second);
ans = min(ans, dis[n][i].first);
}
printf("%lld\n", ans == inf ? -1 : ans);
return ;
};
for (; Tcs; Tcs--) {
solve();
}
return 0;
}