[ZJOI2006]物流运输（最短路辅助dp）

题目：

个点的无向图，货车要连续天将货物从结点运到结点，货车走过一条边的代价=边的长度。其中会给一些限制，即结点在天内无法使用。货车每换一次运输路线需要花费的代价。问货车天将货物从结点运到结点的最小代价。

做法：

由于和的规模比较小。我们要打破固有的图论思维做这道题。
设为货车前天运送货物的最小代价。我们可以枚举上一次更换运输路线的时间点来转移。因为当确定了天运输路线不变时，此路线就是这些天里用能用的点跑出来的到的最短路。也就是。
因为和又很小，所以枚举每个都跑一遍最短路转移即可。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 110, M = 25;
const int inf = 0x3f3f3f3f;
int n, m, k, e, d;
int ban[M][N];
vector<pair<int,int> > g[M];
priority_queue<pair<int,int> > q;
int dis[M], can[M], dp[N];
int dijkstra(int l, int r){
    memset(dis, inf, sizeof dis);
    for (int i = 1; i <= m; ++i) can[i] = ((ban[i][r]-ban[i][l-1]) == 0);
    q.push(make_pair(0, 1)); dis[1] = 0;
    while (!q.empty()){
        int u = q.top().second;
        int d = -q.top().first; q.pop();
        if (d != dis[u]) continue;
        for (auto& e : g[u]) if (can[e.first]){
            int v = e.first, w = e.second;
            if (dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
    return dis[m];
}
int main(void){
    IOS;
    cin >> n >> m >> k >> e;
    for (int i = 1; i <= e; ++i){
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }
    cin >> d;
    for (int i = 1; i <= d; ++i){
        int p, a, b; cin >> p >> a >> b;
        ban[p][a]++, ban[p][b+1]--;
    }
    for (int i = 1; i <= m; ++i){
        for (int j = 1; j <= n; ++j) ban[i][j] += ban[i][j-1];
        for (int j = 1; j <= n; ++j) ban[i][j] = ban[i][j-1]+(ban[i][j] > 0);
    }
    memset(dp, inf, sizeof dp); dp[0] = -k;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= i; ++j) if (dp[j-1] != inf){
            int x = dijkstra(j, i); if (x == inf) continue;
            dp[i] = min(dp[i], dp[j-1]+x*(i-j+1)+k);
        }
    }
    cout << dp[n] << endl;
    return 0;
}