图论专题的第一题。其实很分层图模板。

建立分层图，$(u,h)$ 这个点表示到达点 $u$ 疲劳值为 $h$ 时候的最短距离。那么最短路的时候就可以分类讨论两种转移了。

不需要显式建立分层图，具体转移方法如下： - 假如 $h_u>h_v$ 的话，就相当于这些边 $\forall 0\leq i\leq H,(u,i)\to (v,0)$ 这么做。 - 否则相当于 $(u,i)\to (v,i+h_v-h_u)$ 这些边这么做。

具体的做法，跟 dijkstra 模板一样，假如计算得到的距离更小，那么就更新距离，并且把这个点塞到优先队列中。

时间复杂度 $O(nH\log (nH))$，空间复杂度 $O(nH)$。

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++ )
#define per(i, l, r) for(int i = (l); i >= (r); i -- )
#define frein(s) freopen(s, "r", stdin)
#define freout(s) freopen(s, "w", stdout)
#define int long long
#define endl '\n'
using namespace std;

constexpr int N = 1e4 + 5;
constexpr int H = 100 + 5;
constexpr int INF = 0x3f3f3f3f3f3f3f3f;
int n, m, dis[N][H], mh, h[N];
bool vis[N][H];
vector<pair<int, int> > g[N];
struct Node {
    int u, h, dis;
    Node(int _u = 0, int _h = 0, int _dis = 0) : u(_u), h(_h), dis(_dis) {}
    bool operator > (const Node &t) const {
        return dis > t.dis;
    }
};
priority_queue<Node, vector<Node>, greater<Node> > q;

void dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    q.push(Node(1, 0, 0));
    dis[1][0] = 0;
    while(!q.empty()) {
        Node u = q.top();
        q.pop();
        if(vis[u.u][u.h]) continue;
        vis[u.u][u.h] = true;
        for(auto p : g[u.u]) {
            int v = p.first, w = p.second;
            if(h[v] < h[u.u]) {
                rep(i, 0, mh) {
                    if(dis[v][0] > dis[u.u][i] + w) {
                        dis[v][0] = dis[u.u][i] + w;
                        q.push(Node(v, 0, dis[v][0]));
                    }
                }
            } else {
                rep(i, 0, mh - h[v] + h[u.u]) {
                    int nh = i + h[v] - h[u.u];
                    if(dis[v][nh] > dis[u.u][i] + w) {
                        dis[v][nh] = dis[u.u][i] + w;
                        q.push(Node(v, nh, dis[v][nh]));
                    }
                }
            }
        }
    }
}

signed main() {
    frein("trail.in"), freout("trail.out");
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> mh;
    rep(i, 1, n) cin >> h[i];
    rep(i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    dijkstra();
    rep(i, 2, n) {
        int res = INF;
        rep(j, 0, mh) res = min(res, dis[i][j]);
        cout << (res == INF ? -1 : res) << " ";
    }
    return 0; 
}