BZOJ1003: [ZJOI2006] 物流运输 trans

物流运输……看了神犇的题解，就是dp+最短路，设f[i]为1~i天的最少花费，那么

dp[i]=min(cost[1,i],min{dp[j]+cost[j+1,i]+K,1≤j<i})

就是从第一天到第i天不变或者从某一个之前的状态转移过来。

---

具体实现比较简单了。有个细节，就是如何表示某个码头从da天到db天开不开放，用了一个s数组。设f(i)开放为0，不开放为1，那么当仅∑i=dadbf(i)=0 时，从da天到db天码头i畅通无阻。所以用一次区间累加，再用一次求前缀和总计两次求和，得到s数组。（应该就是离散的积分）

画个图：

贴代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <algorithm> 
using namespace std;

const int MAXN = 110, MAXV = 25, MAXE = 500, INF = 0x3f3f3f3f; 
struct edge{int to, cost, next;} es[MAXE];
int head[MAXV];
int s[MAXV][MAXN];
int dp[MAXN];           //1~i天总最小花费 
int N, K, M, E, tot; 

inline void add2(const int &a, const int &b, const int &cost){
    es[tot] = (edge){b, cost, head[a]}; head[a] = tot++;
    es[tot] = (edge){a, cost, head[b]}; head[b] = tot++;
}

int d[MAXV], vis[MAXV];
int SPFA(int da, int db){
    queue<int> que;
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    que.push(1); vis[1] = 1; d[1] = 0;
    while(!que.empty()){
        int u = que.front(); que.pop(); vis[u] = 0;
        for(int i = head[u]; i != -1; i = es[i].next){
            int v = es[i].to;
            if(s[v][db] - s[v][da-1]) continue;
            if(d[v] > d[u] + es[i].cost){
                d[v] = d[u] + es[i].cost;
                if(!vis[v]){
                    que.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
//  printf("day%d~day%d cost %d
", da, db, d[M]);
    return d[M];
}

int main(){
    freopen("in.txt", "r", stdin);
    scanf("%d%d%d%d", &N, &M, &K, &E);

    memset(head, -1, sizeof(head));
    int a, b, cost;
    for(int i = 0; i < E; ++i){
        scanf("%d%d%d", &a, &b, &cost);
        add2(a, b, cost);
    }
    int d, v;
    scanf("%d", &d);
    for(int i = 0; i < d; ++i){
        scanf("%d%d%d", &v, &a, &b);
        ++s[v][a];
        --s[v][b+1];
    }
    for(int k = 0; k < 2; ++k){
        for(v = 1; v <= M; ++v){
            for(int i = 1; i <= N; ++i){
                s[v][i] += s[v][i-1];
            }
        }
    }
//  for(v = 1; v <= M; ++v){
//      for(int i = 1; i <= N; ++i){
//          printf("s[%d][%d]=%d
", v, i, s[v][i]);
//      }
//  }
    for(int i = 1; i <= N; ++i){
        dp[i] = SPFA(1, i);
        if(dp[i] < INF) dp[i] *= i;
        for(int j = 1; j < i; ++j){
            int cost = SPFA(j + 1, i);
            if(cost < INF)
                dp[i] = min(dp[i], dp[j] + K + cost * (i - j));
        }
    }
    printf("%d
", dp[N]);
    return 0;
}