c/c++语言开发共享bzoj1003: [ZJOI2006]物流运输(最短路+DP)

题目：

1003: [zjoi2006]物流运输

解析：

最短路+dp
我们用(no[i][j])来表示(i)在第(j)天不可以经过
用(cost[i][j])表示第(i)天到第(j)天的花费
在最短路的时候判断一下在第(i)天到第(j)天中哪些码头不可以走，在做最短路时跳过

最后设f[i]表示到第i天时的最小花费
转移方程
(f[i] = min(f[i], f[j]+k+cost[j+1][i]*(i-j)))

代码：

#include <bits/stdc++.h>  using namespace std;  const int n = 1010; const int inf = 0x3f3f3f3f;  int n, m, k, e, num, t; int head[n], dis[n];  long long f[n], cost[n][n];  bool vis[n], no[n][n], mark[n];  struct node {     int v, nx, w; } e[n];  struct edge {     int id, dis;     bool operator <(const edge &oth) const {         return dis > oth.dis;     } };  inline void add(int u, int v, int w) {     e[++num] = (node) {v, head[u], w}, head[u] = num; }  priority_queue<edge>q; void dijkstra(int s, int from, int to) {     memset(dis, inf, sizeof dis);     memset(vis, 0, sizeof vis);     memset(mark, 0, sizeof mark);     for (int i = 1; i <= m; ++i)         for (int j = from; j <= to; ++j)             if (no[i][j]) mark[i] = 1;     dis[s] = 0;      q.push((edge) {s, 0});     while (!q.empty()) {         int u = q.top().id;         q.pop();         if (vis[u]) continue;         vis[u] = 1;         for (int i = head[u]; ~i; i = e[i].nx) {             int v = e[i].v;             if (mark[v]) continue;             if (dis[v] > dis[u] + e[i].w)                  q.push((edge) {v, dis[v] = dis[u] + e[i].w});         }     } }  signed main() {     memset(head, -1, sizeof head);     cin >> n >> m >> k >> e;     for (int i = 1, x, y, z; i <= e; ++i) {         cin >> x >> y >> z;         add(x, y, z), add(y, x, z);     }     cin >> t;     for (int i = 1, x, y, z; i <= t; ++i) {         cin >> x >> y >> z;         for (int j = y; j <= z; ++j) no[x][j] = 1;     }     for (int i = 1; i <= n; ++i)         for (int j = i; j <= n; ++j) {             dijkstra(1, i, j);             cost[i][j] = dis[m];         }     for (int i = 1; i <= n; ++i) ;     for (int i = 1; i <= n; ++i) {         f[i] = cost[1][i] * i;         for (int j = 1; j <= i; ++j) {             f[i] = min(f[i], f[j] + k + cost[j + 1][i] * (i - j));         }     }     cout << f[n]; }