这道题我是拿状压做的，虽然慢了点（#滑稽）
　因为m<=20，且1，m,不受限制所以可以说m<=18这样状压就妥妥的了。我们完全可以先预处理出来在那些点能用的情况下1~m的最短路，然后将所有可行解建一个链表，缩短时间，然后再算出来每一天那些码头不能用，然后传统DP就好了。

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
int t,n,m,k,zz,d;
struct ro{
    int to,l;
    int next;
}road[1000];
int a[40];
void build(int x,int y,int z){
    zz++;
    road[zz].to=y;
    road[zz].next=a[x];
    road[zz].l=z;
    a[x]=zz;
}
int dis[(1<<18)+5][21];
int q[200],zt[105],head,en;
bool rd[200];
bool yx;
int pre[(1<<18)+5];
bool spfa(int tt){
    memset(q,0,sizeof(q));
    head=1,en=0;
    dis[tt][1]=0;
    rd[1]=1;
    en++;
    q[en]=1;
    while(en>=head)
    {
        int x=q[head];
        head++;
        rd[x]=0;
        for(int i=a[x];i>0;i=road[i].next)
        {
         
            int y=road[i].to;
            if(y==n||(1<<(y-2)&tt))
            {
                if(dis[tt][y]>dis[tt][x]+road[i].l)
                {
                    dis[tt][y]=dis[tt][x]+road[i].l;
                    if(!rd[y])
                    {
                        rd[y]=1;
                        en++;
                        q[en]=y;
                    }
                }
            }
        }
    }
    if(dis[tt][n]!=dis[tt][0])
        return 1;
    return 0;
}
int f[2][(1<<18)+5];
int main(){
    memset(pre,-1,sizeof(pre));
    memset(dis,0x3f,sizeof(dis));
    scanf("%d%d%d%d",&t,&n,&k,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        build(x,y,z);
        build(y,x,z);
    }
    int lla=0;;
    for(int i=0;i<(1<<(n-2));i++)
    {
        if(spfa(i))
        {
            if(i==0) yx=1;
            pre[lla]=i;
            lla=i;
        }
    }
    scanf("%d",&d);
    for(int i=1;i<=d;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        for(int j=y;j<=z;j++)
            zt[j]|=(1<<(x-2));
    }
    int la=1,now=0,mn=-k;
    for(int i=1;i<=t;i++)
    {
        swap(la,now);
        int mn2=0x7fffffff;
        for(int j=0;j!=-1;j=pre[j])
        {
            if((j&zt[i])||((!yx)&&j==0)) continue;
            if(f[la][j])
            {
                f[now][j]=min(f[la][j]+dis[j][n],mn+k+dis[j][n]);
                mn2=min(mn2,f[now][j]);
            }
            else
            {
                f[now][j]=mn+k+dis[j][n];
                mn2=min(mn2,f[now][j]);
            }
        }
        memset(f[la],0,sizeof(f[la]));
        mn=mn2;
    }
    printf("%d\n",mn);
    //while(1);
    return 0;
}

WA*n
于是拿vijos试水保ac率
应该在填表的时候先初始化f[i]=t[1][i] 就不用在最后-K了
先用最短路预处理 然后dp
t[i][j]表示i~j天只走一条最短路的花销
f[i]表示到第i天的最少花销
边界f[0]=0 f[i]=t[1][i]
然后f[i]=min(f[i],f[j]+t[j+1][i]+K) K为换路的费用 0<=j

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n, m, K, E,d;
struct edge {
    int v, nxt,w;
}e[801];    //n*n*2 无向图
int p[21], eid=0;
long long dist[21], t[101][101],f[101];     //t表示i~j天都走同一路线的最短路
inline void ins(int u,int v,int w) {
    eid++; e[eid].v = v; e[eid].w = w; e[eid].nxt = p[u]; p[u] = eid;
}
inline void ins2(int u, int v, int w) {
    ins(u, v, w); ins(v, u, w);
}
inline int read() {
    int x; scanf("%d", &x); return x;
}

bool ava[21],book[101][21];
void spfa() {
    bool inq[21];
    queue<int> q;
    //memset(ava, true, sizeof(ava));
    memset(dist, 0x3f, sizeof(dist));
    memset(inq, false, sizeof(inq));
    q.push(1); inq[1] = true;
    dist[1] = 0;
    while (!q.empty()) {                        //预处理每个时刻的最短路
        int u = q.front();
        q.pop();
        int v;
        inq[u] = false;
        for (int i = p[u]; i; i = e[i].nxt) {
            v = e[i].v;
            if(ava[v])
                if (dist[u] + e[i].w < dist[v])
                {
                    dist[v] = dist[u] + e[i].w;
                    if (!inq[v]) {
                        inq[v] = 1; q.push(v);
                    }
                }
        }
    }
}

void solve() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            memset(ava, true, sizeof(ava));
            for(int k=1;k<=m;k++)
                for(int l=i;l<=j;l++)
                    if(!book[l][k]) //第l天k不能用
                    {
                        ava[k] = false;
                        break;
                    }
            spfa();
            dist[m] >= 0x3f ? t[i][j] = dist[m] : t[i][j] = dist[m] * (j - i + 1);
        }
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; i++)        //处理每一天
    {
        f[i] = t[1][i];
        for (int j = 0; j < i; j++) {       //前j-1天的最小花销+j~i天的最短路之和+K(换路花销）
            f[i] = min(f[i], f[j] + t[j + 1][i] + K);
        }
    }
}
int main() {
    scanf("%d%d%d%d", &n, &m, &K, &E);
    memset(book, true, sizeof(book));
    for (int i = 1; i <= E; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        ins2(x, y, z);
    }
    scanf("%d", &d);
    for (int i = 0; i < d; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        for (int j = y; j <= z; j++)
            book[j][x] = false; //标记是否可用
    }
    solve();
    cout <<f[n];
    //system("pause");
    return 0;
}