第一眼 点数 很小所以状压。
第二眼发现复杂度炸了。
然后换了一个 dp 状态：设 $dp_i$ 表示前 $i$ 天的最小花费。
然后直接转移即可，至于路径长度直接 dijkstra 即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 115, M = 415;
int n, m, day, k, q;
int h[N], e[M], w[M], ne[M], idx = 0;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int cant[N];
bool vis[N], st[N];
long long d[N], dist[N][N], dp[N];

int dijkstra() {
    for (int i = 1; i <= n; i++) d[i] = 0x3f3f3f3f, st[i] = 0;
    priority_queue< pair<int, int> > q;
    d[1] = 0;
    q.push(make_pair(0, 1));
    while (q.size()) {
        int u = q.top().second; q.pop();
        if (st[u]) continue;
        st[u] = 1;
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (vis[v]) continue;
            if (d[v] > d[u] + w[i]) {
                d[v] = d[u] + w[i];
                q.push(make_pair(-d[v], v));
            }
        }
    }
    return d[n];
}

int main() {
    scanf("%d%d%d%d", &day, &n, &k, &m);
    for (int i = 1; i <= n; i++) h[i] = -1;
    for (int i = 1, a, b, c; i <= m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    scanf("%d", &q);
    while (q--) {
        int u, l, r; scanf("%d%d%d", &u, &l, &r);
        for (int i = l; i <= r; i++) cant[i] |= (1 << u - 1);
    }
    for (int i = 1; i <= day; i++) {
        for (int j = 1; j <= n; j++) vis[j] = 0;
        for (int j = i; j <= day; j++) {

            for (int k = 1; k <= n; k++)
                if (cant[j] & (1 << k - 1)) vis[k] = 1;

            dist[i][j] = dijkstra();
        }
    }
    // for (int i = 1; i <= n; i++, puts(""))
    //     for (int j = i; j <= n; j++) cout << dist[i][j] << ' ';
    for (int i = 1; i <= day; i++) dp[i] = 1e18;
    for (int i = 1; i <= day; i++)
        for (int j = 0; j < i; j++) {
            dp[i] = min(dp[i], dp[j] + dist[j + 1][i] * 1ll * (i - j) + k);
        }
    printf("%lld\n", dp[day] - k);
    return 0;
}