Luogu1772 [ZJOI2006] 物流运输

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

#define int long long // 不开longlong见祖宗
const int Days = 105, N = 25, M = 405;

int n, m, k, e, Q, x, y, w;
int la[N], en[M], ne[M], len[M], idx;
int dis[N], f[Days], cost[Days][Days];
bool st[N], lock[N], timlock[N][Days];
queue<int > q;

void add(int x, int y, int z) {
	en[ ++ idx] = y;
	ne[idx] = la[x];
	la[x] = idx;
	len[idx] = z;
}

void spfa(int l, int r) {
    memset(dis, 0x3f3f3f3f, sizeof dis);
    q.push(1), dis[1] = 0, st[1] = 1;
    while(q.size()) {
        int u = q.front();
        st[u] = 0; q.pop();
        for (int i = la[u]; i; i = ne[i]) {
            int v = en[i];
            if(lock[v]) continue;
            if(dis[v] > dis[u] + len[i]) {
                dis[v] = dis[u] + len[i];
                if(!st[v]) {
                    q.push(v);
                    st[v] = 1;
                }
            }
        }
    }
    cost[l][r] = (dis[m]>=0x3f3f3f3f3f3f3f3f ? 1 : r - l + 1) * dis[m];
}

signed main(){
	ios::sync_with_stdio(0);
	
	cin >> n >> m >> k >> e;
	while(e -- ) {
		cin >> x >> y >> w;
		add(x, y, w); add(y, x, w); // 注意是双向边
	}
	cin >> Q;
	while(Q -- ) {
		cin >> w >> x >> y;
		for (int i = x; i <= y; ++ i ) timlock[w][i] = 1; //打标记
	}
	
	for (int i = 1; i <= n; ++ i ) 
		for (int j = i; j <= n; ++ j ) {
			for (int l = 1; l <= m; ++ l )
				for (int tim = i; tim <= j; ++ tim ) {
					lock[l] |= timlock[l][tim];
					if(lock[l]) break;
				}
			spfa(i, j);
			for (int l = 1; l <= m; ++ l ) lock[l] = 0; //记得清空
		} 
	
	for (int i = 1; i <= n; ++ i ) {
		f[i] = cost[1][i]; //初始化为全用一条路
		for (int j = 1; j < i; ++ j ) {
			f[i] = min(f[i], f[j] + k + cost[j + 1][i]);
		}
	}
	
	cout << f[n];
	return 0;
}