DP+最短路
可以先用 \(Dijkstra\) 将每一段时间内的费用都先预处理出来， \([i,j]\) 时间段的费用表示为 \(Cost(i,j)\) ，然后再设 \(dp[i]\) 为第 \(i\) 天时的最优解。状态转移的时候枚举第几天的时候改变了路线。
\[dp[i]=\min_{0≤j<i} \{dp[j]+Cost(j+1,i)*(i-j)+k\}\]
\[dp[0]=-k\]#include#include #include #include const int max_n = 100 + 5;const int max_m = 20 + 5;const int max_e = max_m * max_m + 5;const int inf = 0x3f3f3f3f;int N, M, K, E, D, Tot;int Dp[max_n], First_edge[max_m], P[max_m][max_n], Flag[max_m], Dis[max_m], C[max_n][max_n];struct Edge{ int to, w, next_edge;}Linker[max_e << 1];struct Heap{ int cur; Heap(int x) { cur = x; } bool operator < (const Heap &x) const { return Dis[cur] > Dis[x.cur]; }};std::priority_queue Q;inline int read(){ register int x = 0; register char ch = getchar(); while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); } return x;}inline void add_edge(int x, int y, int z){ Linker[++Tot].to = y; Linker[Tot].w = z; Linker[Tot].next_edge = First_edge[x]; First_edge[x] = Tot;}int Dijkstra(){ int from, to, w; memset(Dis, inf, sizeof(Dis)); Dis[1] = 0; Q.push(Heap(1)); while(!Q.empty()) { from = Q.top().cur; Q.pop(); for(int k = First_edge[from]; k; k = Linker[k].next_edge) { to = Linker[k].to; w = Linker[k].w; if(Dis[to] > Dis[from] + w && !Flag[to]) { Dis[to] = Dis[from] + w; Q.push(Heap(to)); } } } return Dis[M];}int main(){ int x, y, z; N = read(); M = read(); K = read(); E = read(); for(int i = 1; i <= E; ++i) { x = read(); y = read(); z = read(); add_edge(x, y, z); add_edge(y, x, z); } D = read(); for(int i = 1; i <= D; ++i) { x = read(); y = read(); z = read(); for(int j = y; j <= z; ++j) P[x][j] = 1; } for(int i = 1; i <= N; ++i) { for(int j = i; j <= N; ++j) { memset(Flag, 0, sizeof(Flag)); for(int k = 1; k <= M; ++k) for(int l = i; l <= j; ++l) Flag[k] |= P[k][l]; C[i][j] = Dijkstra(); } } memset(Dp, inf, sizeof(Dp)); Dp[0]= -K; for(int i = 1; i <= N; ++i) for(int j = 0; j < i; ++j) Dp[i] = std::min(Dp[i], (C[j + 1][i] == inf) ? inf : Dp[j] + C[j + 1][i] * (i - j) + K); printf("%d\n", Dp[N]); return 0;}