题意：m个点e条边的无向图（1≤m≤20），把货物从1运到m，一些点在有一些时段里不可用，求n天的花费最少的运输方案（n≤100）。花费等于路径长度之和加上K*路径变更的次数。
无意中看过这道题的tag：最短路+DP，所以也不能完全算作是自己想出来的。QAQ
“路径变更的次数”使我们想到把一段时间内不变的路径放到一起处理，划分DP的模型自然地显现出来。计算转移的代价每次跑SPFA或Dijkstra就好，虽然我选择的是Floyd……
可以动态加点，但是这里暴力地跑就够用了。
可以用前缀和快速判断点是否可用。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = 100, MAX_M = 20, inf = 0x3f3f3f3f;
int m, w[MAX_M+1][MAX_M+1], b[MAX_M+1][MAX_N+2], f[MAX_N+1];template<typename T>
inline void relax(T& x, T v)
{x = min(x, v);
}int floyd(int fr, int to)
{static int d[MAX_M+1][MAX_M+1], l[MAX_M+1];memcpy(d, w, sizeof(w));int n = 0;for (int i = 1; i <= m; ++i)if (!(b[i][to] - b[i][fr-1]))l[++n] = i;for (int k = 1; k <= n; ++k)for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)relax(d[l[i]][l[j]], d[l[i]][l[k]] + d[l[k]][l[j]]);return d[1][m];
}int main()
{int n, K, e;scanf("%d %d %d %d", &n, &m, &K, &e);memset(w, 0x3f, sizeof(w));for (int i = 1; i <= m; ++i)w[i][i] = 0;while (e--) {int u, v, c;scanf("%d %d %d", &u, &v, &c);relax(w[u][v], c);relax(w[v][u], c);}int d;scanf("%d", &d);while (d--) {int p, u, v;scanf("%d %d %d", &p, &u, &v);++b[p][u];--b[p][v+1];}for (int i = 1; i <= m; ++i)for (int j = 1; j <= n; ++j)b[i][j] += b[i][j-1];for (int i = 1; i <= m; ++i)for (int j = 1; j <= n; ++j)b[i][j] += b[i][j-1];f[0] = -K;for (int i = 1; i <= n; ++i) {f[i] = inf;for (int j = 0; j < i; ++j) {int t = floyd(j+1, i);if (t < inf)relax(f[i], f[j] + t*(i-j) + K);}}printf("%d\n", f[n]);return 0;
}