5 5 10 8
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 532
声明：次解答来自洛谷作者 DavidJing，本人只是作出解答解析
题意
给你m个码头，n天，其中一些码头在某些天会损坏，这n天都要有一条路从1->m，每一次更换道路会需要K的价值，求这n天每天从1到m的距离和与更改道路的价值之和的最小值.
解题思路：
最优解问题明显就是一个dp，而求两点之间的距离当然就是最短路了~
那么思考怎么构建dp方程
首先我们可以设f[i]表示前i天所花费的最小值
f[i]=min(f[i],f[j-1]+(i-j+1)
* L+K) （1<=j<=i)
什么意思呢 就是第j天到第i天走同一条路，并且这条路和第j-1天是不同的
那么第j天到第i天走的肯定是此时情况下的最短路了,所以L表示在当前情况下的1->m的最短路,可以用spfa或dijktra求解
那么现在就要考虑码头无法使用的情况了，
因为我们要保证第j天到第i天走的最短路是不能包括在这些天内不能经过的点的(哪怕是1天或是间断的几天都不行)
所以我们枚举j的时候可以从大到小枚举，并且将第j天无法通过的点同j+1->i天无法通过的点塞入一个集合，并且在求最短路时判断不经过集合中的点，
就可以求出从第j天到第i天经过未损坏的点从1到m的最短路了~
L这样求解，题目也就容易做出了~
*/
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace
std;
const int
maxn=1005;
const int
maxm=2005;
int
ans,tot,a,b,c,d,n,m,K,e;
int
dp[maxn],now[maxm],ff[maxn][maxm],cost[2*maxm],f[maxm],q[5*maxm],dis[maxm],DIS[maxn],nex[2*maxm],lnk[maxm],las[2*maxm];
//这里是图的邻接链表存储
//思想方法：
//用两个数组分别取出同一个起点的所有边，并临时存储边的序号lnk，取出后转存到另外一个数组las里
//这时要注意“下一条边”这个说法，我们将每个起点的第一条边初始化为一个不存在的序号，那么
//取出第一条实际序号的边前将这个不存在的序号存入以第一次次找到的边的序号为下标的数组las里面
// 然后将第一条实际边的序号存入临时数组lnk，以后每找到以同一个点为起点的边时都先将上一次找到的
//以这个点为起点的上一条边的序号存到以这条边的序号为下标的数组里面 最后lnk数组里面存储的是
//以同一个点为起点的最后一条边的序号
//这样“取图”的时候，就可以根据点来找以每个点为起点的边
//因为同一个起点的最后一条边的序号可以直接从lnk数组取出，
//接下来的“下一条边”的序号可以从以上一条边的序号为下标的las数组里面取出
//终点存入nex数组，将与起点相连的“下一条边”的边的序号存入las数组，
//将与起点相连的“最后一条边”的序号存入lnk数组 ,将边长存入cost数组
void add(int x,int
y,int z)
{nex[++tot]=y;las[tot]=lnk[x];lnk[x]=tot;cost[tot]=z;}
//保证输入的是数字
int read()
{
int
ch=0,x=0;while(ch=getchar(),ch<'0'||ch>'9');//输入的如果不是数字字符就一直输入
while(x=x*10+ch-48,ch=getchar(),ch>='0'&&ch<='9');//若是数字字符就转化为相应的数字
return x;
}
//spfa算法求最短路
/*算法思想：
spfa算法是bellman-Ford算法的队列优化
初始化所有点到源点的距离为无穷大
队列的头指针head和尾指针tail都指向队列的第一个位置
将源点放入队列中，尾指针tail++指向队列下一个位置
从源点出发，遍历所有与源点相连的边，如果通过源点和这条边能够使得这条边的
下一个点到源点的距离变得更短就更新“下一个点”到源点的距离，并将这个点加入队列里面，tail++。这样的操作，我们称作“松弛”
同样的，源点为起点的所有边的“下一个点”到源点的距离都松弛后， 源点出队head++，头指针指向队列下一个位置
接着再以队列下一个位置上的点为起点遍历所有与它相连的边，对所有的“下一个点”进行松弛，依此类推
注意先前加入队列的点之后就不用了再次加入了，这用一个标记数组就可以搞定
所有的点都遍历过后，就能求出所有点到源点的最短距离
这是一个边的松弛过程
//spfa算法可参考：https://www.cnblogs.com/thousfeet/p/9229395.html
*/
int spfa()
{
memset(dis,127,sizeof(dis));
int head=1,tail=1;q[1]=1;dis[1]=0;f[1]=1;//头指针和尾指针都指向队列第一个位置 ，将码头1入队，初始距离为0，码头1标记为已在队列中
while(head<=tail)
{
int u=q[head];//源点入队
for(int k=lnk[u];k;k=las[k])//lnk数组存储与起点相连的边的序号，las数组存储的是与起点相连的“下一条边”的序号
if(dis[nex[k]]>dis[u]+cost[k]&&(!now[nex[k]]))//nex数组存储的是边的终点，cost数组存储的是边的长度，
//dis数组存储的是点到源点的最短距离，now数组存储的是当前点是否不能通过
{
dis[nex[k]]=dis[u]+cost[k];
if(!f[nex[k]])//f数组存储的是当前点是否在队里
{
f[nex[k]]=1;
q[++tail]=nex[k];//将当前点入队
}
}
f[u]=0;//将起点出队
head++;
}
return dis[m];//对于每条路线都返回终点到源点的最短距离,
}
int main()
{
n=read();m=read();K=read();e=read();//输入天数、码头数、成本、航线总数
for(int i=1;i<=e;i++)
{
a=read();b=read();c=read();
add(a,b,c);add(b,a,c);//输入双向航线起点、终点、长度
}
d=read();//d组数据表示码头从某天到某天无法通行
for(int i=1;i<=d;i++)
{
a=read();b=read();c=read();
for(int j=b;j<=c;j++)
ff[j][a]=1;//ff数组存储a码头第j天无法通行
}
//用动态规划求最低成本
memset(dp,63,sizeof(dp));
dp[0]=-K;//第一次选择路径是不算做跟改路径的
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) now[j]=0;//初始化所有码头都可以通行
for(int j=i;j>=1;j--)
{
for(int k=1;k<=m;k++)
if(ff[j][k])now[k]=1;//now[k]表示第j天到第i天k是无法使用的
int get=spfa();//计算第j天到第i天的最短路径
if(get>=100000000)break;//j->i天无法通过一条固定路径到达就退出，后面也不可能到达
dp[i]=min(dp[i],dp[j-1]+(i-j+1)*get+K);//前i天的最低成本等于前j-1天最低成本加上i->j天成本与前i天最低成本的较小值
}
}
cout<<dp[n];
return 0;
}