前言

菜菜菜菜死了呜呜呜
一开始写了个非常暴力的dfs，还把路径装进vector套进map进行dp，以为复杂度是对的，然后狠狠的tle了，细细一想回溯的这种dfs爆搜一张图，复杂度应该是N^N吧。
dij的重载运算符写反大于号了，debug一小时

题意

物流运输
题意好长。。。说不清了。

分析

答案的设计，可以看成一个数组，一定可以分成很多段，一段之内，走的路径必然是相同的。这条路，必然是最短路。
于是这题就能很愉快的暴力dp了。经典的f[i]表示到第i天的最短花费，因为是一段一段的，所以可以枚举右端点，再枚举左端点开始dp。
这类dp一旦想到状态，方程就能秒出，很简单的递推就出来了。

struct node
{
    int x, val;
    bool operator < (const node &k) const
    {
        return val > k.val;
    }
};
vector<node> v[N];
bool vis[N], not_yet[N][25][25];
int f[N], dis[N];
int n, m, K;
void solve()
{
    int e;
    cin >> n >> m >> K >> e;
    for (int i = 1; i <= e; i++) 
    {
        int x, y, val;
        cin >> x >> y >> val;
        v[x].push_back({y, val});
        v[y].push_back({x, val});
    }   
    int d;
    cin >> d;
    for (int i = 1; i <= d; i++)
    {
        int p, l, r;
        cin >> p >> l >> r;
        for (int j = l; j <= r; j++)
        {
            //第j天，p连接到k和k连接到p都失败
            for (int k = 1; k <= m; k++) not_yet[j][p][k] = not_yet[j][k][p] = 1;
        }
    } 
    fill(f + 1, f + 1 + n, 1e18);
    for (int r = 1; r <= n; r++) //枚举右端点
    {
        for (int l = 1; l <= r; l++)
        {
            fill(vis + 1, vis + 1 + m, false);
            fill(dis + 1, dis + 1 + m, 1e15);
            priority_queue<node> q;
            q.push({1, 0});
            dis[1] = 0;
            while(!q.empty())
            {
                int x = q.top().x;
                q.pop();
                if (vis[x]) continue;
                vis[x] = 1;
                for (auto &i : v[x])
                {
                    int y = i.x, val = i.val;
                    if (val + dis[x] < dis[y])
                    {
                        bool ok = 1;
                        for (int k = l; k <= r; k++)
                        {
                            if (not_yet[k][x][y])
                            {
                                ok = 0;
                                break;
                            }
                        }
                        if (!ok) continue;
                        dis[y] = val + dis[x];
                        q.push({y, dis[y]});
                    }
                }
            }
            if (dis[m] > 1e14) continue;
            f[r] = min(f[r], f[l - 1] + (r - l + 1) * dis[m] + K);  //炸long long了，不要乱用1e18
        }
    }
    cout << f[n] - K;
}