#include <cstring>
#include <iostream>
#include <algorithm>
#define min(x, y) ((x)<(y)?(x):(y))

typedef long long ll;

const int N = 21;

int n, m, cost, tmp, s[101], e[N][N], dis[N];
ll f[101];
bool vis[N];

void dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));

    dis[0] = 0;
    for (int i=1; i<m; ++i) {
        int u = 0, minn = 0x3f3f3f3f;
        for (int j=0; j<m; ++j) {
            if (!(tmp & (1<<j)) && dis[j] < minn && !vis[j]) {
                u = j; minn = dis[j];
            }
        }
        vis[u] = 1;
        for (int v=0; v<m; ++v) {
            if (!(tmp & (1<<v)) && dis[v] > dis[u] + e[u][v])
                dis[v] = dis[u] + e[u][v];
        }
    }
}

int main(void) {
    std::ios::sync_with_stdio(false);

    std::cin >> n >> m >> cost >> tmp;
    memset(e, 0x3f, sizeof(e));
    for (int i=1,u,v,w; i<=tmp; ++i) {
        std::cin >> u >> v >> w;
        e[--u][--v] = e[v][u] = min(e[u][v], w);
    }
    std::cin >> tmp;
    for (int i=1,p,a,b; i<=tmp; ++i) {
        std::cin >> p >> a >> b; p--;
        for (int j=a; j<=b; ++j) s[j] |= (1 << p);
    }

    memset(f, 0x3f, sizeof(f));
    f[0] = -cost;
    for (int i=1; i<=n; ++i) {
        for (int j=i; j<=n; ++j) {
            tmp = 0;
            for (int k=i; k<=j; ++k) tmp |= s[k];
            dijkstra();
            if (dis[m-1] == 0x3f3f3f3f) break;
            f[j] = min(f[j], f[i-1] + dis[m-1] * (j - i + 1) + cost);
        }
    }

    std::cout << f[n] << '\n';

    return 0;
}

大概思路：枚举一段时间并找到此时段内一直可行的最短路，然后加上消耗，判断码头能否经过用了二进制，求查错，或者hack