\(g[i][j]\)表示不走在
\(i\text{~}j\)时间段中会关闭的港口（哪怕只关
\(1\)天）从
\(1\)到
\(m\)的最短路。
\(f[i]\)表示前
\(i\)天的最小花费。于是有：
\[f[i]=\min_{j=0}^{i-1}[f[j]+g[i][j]*(i-j)+k]\] 就是枚举在哪天改计划。。
边界
\(f[0]=-k\)因为初始计划不算改。其它均为
\(INF\)。
#include #include #include #define INF 1000000000using namespace std;const int MAXM = 25;const int MAXN = 110;const int MAXD = 10010;inline int read(){ int s = 0, w = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * w;}struct Edge{ int next, to, dis, id;}e[MAXN * MAXN << 1];int head[MAXN], num;inline void Add(int from, int to, int dis, int id){ e[++num] = (Edge){ head[from], to, dis, id }; head[from] = num; e[++num] = (Edge){ head[to], from, dis, id }; head[to] = num;}int n, m, k, t, a, b, c, d, u;int l[MAXD], r[MAXD], p[MAXD], dis[MAXM], v[MAXM], ban[MAXM], f[MAXN], g[MAXN][MAXN];queue q;int main(){ n = read(); m = read(); k = read(); t = read(); for(int i = 1; i <= t; ++i){ a = read(); b = read(); c = read(); Add(a, b, c, i); } d = read(); for(int i = 1; i <= d; ++i){ p[i] = read(); l[i] = read(); r[i] = read(); } for(int i = 1; i <= n; ++i) for(int j = i; j <= n; ++j){ for(int o = 2; o <= m; ++o) dis[o] = INF, v[o] = ban[o] = 0; for(int o = 1; o <= d; ++o) if(r[o] >= i && l[o] <= j) ban[p[o]] = 1; while(q.size()) q.pop(); q.push(1); while(q.size()){ u = q.front(); q.pop(); v[u] = 0; for(int o = head[u]; o; o = e[o].next) if(!ban[e[o].to] && dis[e[o].to] > dis[u] + e[o].dis){ dis[e[o].to] = dis[u] + e[o].dis; if(!v[e[o].to]) q.push(e[o].to); } } g[i][j] = dis[m]; } for(int i = 1; i <= n; ++i) f[i] = INF; f[0] = -k; for(int i = 1; i <= n; ++i) for(int j = 0; j < i; ++j) f[i] = min(f[i], f[j] + (int)min((long long)INF, (long long)g[j + 1][i] * (i - j)) + k); printf("%d\n", f[n]); return 0;}