bzoj 1003 最短路+dp

首先令cost[i][j]为第i天到第j天都走同一路线的最小花销 这个用SPFA处理
然后就是动规的问题了 令f[i]为1~i天的最小花销
则f[i]=min{ f[j-1]+cost[j][i]+k } ( 1<=j<=i )

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#define INF 0x3f3f3f3f

using namespace std;
typedef long long LL;

struct Edge{
    int v,w;
    Edge(int _v,int _w):v(_v),w(_w){}
};
vector<Edge>E[30];
int n,m,k,e,d;
int past[30][110];//第i个码头第j天能否通过，通过求前缀和判断一段时间内能否都通过
int cost[110][110];//第i天到第j天不变航线的最短航线总长，不存在则为INF
int dp[110];//第1到i天的最小花费

bool vis[30];
int dist[30];
void add(int u,int v,int w){
    E[u].push_back(Edge(v,w));
    E[v].push_back(Edge(u,w));
}
void SPFA(int x,int y){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=m;i++)dist[i]=INF;
    dist[1]=0;
    queue<int>Q;
    while(!Q.empty())Q.pop();
    Q.push(1);
    vis[1]=1;
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        vis[u]=0;
        for(int i=0;i<E[u].size();i++){
            int v=E[u][i].v;
            if(dist[v]>dist[u]+E[u][i].w&&past[v][y]-past[v][x-1]==y-x+1){
                dist[v]=dist[u]+E[u][i].w;
                if(!vis[v]){
                    vis[v]=1;
                    Q.push(v);
                }
            }
        }
    }
    if(dist[m]!=INF){
        cost[x][y]=dist[m]*(y-x+1);
    }
    else cost[x][y]=dist[m];
}

int main(){
    scanf("%d%d%d%d",&n,&m,&k,&e);
    for(int i=1;i<=e;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    scanf("%d",&d);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++)
            past[i][j]=1;
    }
    for(int i=1;i<=d;i++){
        int a,b,p;
        scanf("%d%d%d",&p,&a,&b);
        for(int j=a;j<=b;j++){
            past[p][j]=0;
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=2;j<=n;j++){
              past[i][j]+=past[i][j-1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            SPFA(i,j);
        }
    }
    for(int i=1;i<=n;i++){
        dp[i]=INF;
    }
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(cost[j][i]!=INF){
                dp[i]=min(dp[i],dp[j-1]+cost[j][i]+k);
            }
        }
    }
    printf("%d\n",dp[n]-k);
    return 0;
}