传送门

简化题意

给你 $m$ 个码头，码头之间有双向边连接，$n$ 天，其中一些码头在某些天会不可用，这 $n$ 天都要有一条从 $1$ 到 $m$ 的路，每一次更换道路会需要 $k$ 的代价，求这 $n$ 天每天从 $1$ 到 $m$ 的距离之和与更改道路的价值之和的最小值。

Solution

首先我们能想到一个贪心的策略：在保证最短路的同时，需要保证更换道路尽可能少。

然后0我们可以想到令 $cost_{i,j}$ 为从第 $i$ 天到第 $j$ 天走同一条路径的最短长度和，$f_i$ 为第 $i$ 天的 $ans$ 值，于是我们可以列出状态转移方程：
$$
f_i\ =\ \min \{ f_j + k + cost_{j + 1, i} \}
$$
接下来，我们来处理 $cost{i, j}$，我们发现只要 $x$ 号码头在 $i$ 到 $j$ 天封闭过一次，在 $i$ 到 $j$ 天的路径里就不能选它，所以只需要在跑最短路时判一下 $x$ 号点是否被封禁即可。

注：若 $i$ 到 $j$ 天不能从 $1$ 走到 $m$，就把 $const_{i,j}$ 赋值为 $INF$ 即可。

#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;
}