1003: [ZJOI2006]物流运输 = DP+SBFA

题意就是告诉你有n个点，e条边，m天，每天都会从起点到终点走一次最短路，但是有些点在某些时间段是不可走的，因此在某些天需要改变路径，每次改变路径的成本是K，总成本=n天运输路线长度之和+K*改变运输路线的次数。问如果走才能使得的总成本最小。

首先我们需要标记S这个点，在l到r天范围内，不可走，我们开始肯定是想那么开个数组把，那么开一个数组a[p][j]表示P这个点在第j天是不可走的，然后用链式前向星建边，连接。但是这个题我们改如何才能求到N天的最小成本呢？？？

这个我感觉也是很经典的问题了，DAG上的动态规划啊！！！

我们用一个cost数组表示cost[i][j]中，i到j天范围内的最短路，用一个flag[k] |= a[k][l]表示k点在l天的情况。。。因此我们有一个牛逼的式子

for (int k=;k<=m;k++)

               for (int l=i;l<=j;l++)

                  flag[k]|=a[k][l];

这样就可以表示在L到R区间内的可走性，如果其中任何一个点在L-R天中的任何一天不可用，那么在L到R区间一定不可用

然后我们可以轻易的理工SBFA求出L到R区间内的最短路，最后转化为成本，最后我们我们用一个DP数组，转移方程是

dp[i]=min(dp[i],dp[j]+cost[j+1][i]+k);

意思是我从起点到i点，和从起点到j点，j点到 i 的距离的消耗进行比较，取最后的即可这样我们通过这个小DP，使得范围不断扩大。

最后得到答案

巴特西