其实这道题挺简单的，然而理解错题意导致近几个月都没做出来QAQ

原题：

物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转

停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种

因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是

修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本

尽可能地小。

1<=n<=100，1<=m<=20

 

这道题的意思是说有m个码头，每天从1跑到m，要跑n天（n次），我理解成从1跑到m要跑n天，然后根本没法做嘛qaq

理解题意就好办了，因为数据量很小，所以只需要暴力记录从第i天到第j天都能用的码头，SPFA一下花费，然后DP一下即可

状态方程大概是酱紫：f[i]=min(f[i],dis[j+1][i]*(j-i)+money)，dis是SPFA跑的最短路↑，也就是第i到j天的最小花费

有两点需要注意：

最后的答案要减一次改航线的花费，因为第一次选择航线不用花钱

最后DP的时候要先判断一下dis[j+1][i]是不是+oo，因为如果是+oo的话很有可能乘个(j-i)就爆了

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 struct ddd{
    int next,y,value;}e[210000];int LINK[110000],ltop=0; 8 inline void insert(int x,int y,int z){e[++ltop].next=LINK[x];LINK[x]=ltop;e[ltop].y=y;e[ltop].value=z;} 9 int t,n,money,m;10 bool jin[30][110],can[30];11 int dis[110][110],disf[30];12 int dui[110000],tou=0;13 bool visited[30];14 int f[110];15 void get_cant(int x,int y){16     for(int i=1;i<=n;i++){17         can[i]=true;18         for(int j=x;j<=y;j++)19             if(jin[i][j]){  can[i]=false;  break;}20     }21 }22 void SPFA(int x,int y){23     memset(visited,0,sizeof(visited));24     memset(disf,10,sizeof(disf));25     dui[tou=1]=1;  disf[1]=0;26     for(int k=1;k<=tou;k++){27         visited[dui[k]]=false;28         for(int i=LINK[dui[k]];i;i=e[i].next)if(can[e[i].y])29             if(disf[dui[k]]+e[i].value
           
            >t>>n>>money>>m;44 int _left,_right,_value;45 while(m --> 0){ //趋向于46 scanf("%d%d%d",&_left,&_right,&_value);47 insert(_left,_right,_value),insert(_right,_left,_value);48 }49 cin>>m;50 while(m --> 0){ //趋向于51 scanf("%d%d%d",&_value,&_left,&_right);52 for(int i=_left;i<=_right;i++)53 jin[_value][i]=true;54 }55 for(int i=1;i<=t;i++)56 for(int j=i;j<=t;j++){57 get_cant(i,j);58 SPFA(i,j);59 }60 f[0]=0;61 for(int i=1;i<=t;i++)62 for(int j=0;j
            
             <168430090)//防止下面乘(i-j)的时候爆掉63 f[i]=min(f[i],f[j]+dis[j+1][i]*(i-j)+money);//注意这里是j+1，因为从变的第二天才开始跑这种方案64 cout<
             
              <