题目链接
(g[i][j])表示不走在(i ext{~}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 <cstdio>
#include <queue>
#include <cstring>
#define INF 1000000000
using 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 <int> 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
", f[n]);
return 0;
}