物流运输……看了神犇的题解，就是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\n", 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\n", 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\n", dp[N]);

    return 0;

}