遇到小范围数据的题目就容易被限制了思维，我单知道数据小可以跑很多遍最短路，但我没想到暴力跑N ^ 2的最短路也能过
物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转
停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种
因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是
修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本
尽可能地小。
题意
把这题全部拆开来事实上是一道好题，用cost[i][j]表示i到j这个时间段内都可以跑的最短路，然后直接n ^ 2的dp跑出来答案即可。
时间复杂度n * n * m * lnm,实际上是一个很科学很可以接受的复杂度，但是由于之前10w的题目做得太多了，这种小数据反而被限制了想象力，拆开来想这题就变成了一道综合了基础最短路，基础动态规划，基础前缀和的水题。
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
inline int read(){int now=;register char c=getchar();for(;!isdigit(c);c=getchar());
for(;isdigit(c);now=now*+c-'',c=getchar());return now;}
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
const double eps = 1e-;
const int maxn = ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
int N,M,K,e;
struct Edge{
int to,next;
LL dis;
}edge[];
int head[maxn],tot;
int use[][maxn];
void init(){
Mem(head,-); tot = ;
}
void add(int u,int v,LL w){
edge[tot].to = v;edge[tot].next = head[u];
edge[tot].dis = w;head[u] = tot++;
}
LL cost[maxn][maxn];
bool vis[maxn];
LL dis[maxn];
LL dp[maxn];
struct Node{
int pos; LL dis;
Node(int pos = ,LL dis = ):pos(pos),dis(dis) {}
friend bool operator < (Node a,Node b){
return a.dis > b.dis;
}
};
LL Dijkstra(int l,int r){
for(int i = ; i <= M ; i ++){
if(use[i][r] - use[i][l - ] == ) vis[i] = ;
else vis[i] = ;
dis[i] = INF;
}
dis[] = ;
priority_queue<Node>Q; Q.push(Node(,));
while(!Q.empty()){
Node u = Q.top(); Q.pop();
if(u.dis > dis[u.pos]) continue;
for(int i = head[u.pos]; ~i ; i = edge[i].next){
int v = edge[i].to,w = edge[i].dis;
if(vis[v] && dis[v] > u.dis + w){
dis[v] = u.dis + w;
Q.push(Node(v,dis[v]));
}
}
}
if(dis[M] == INF) return INF;
return dis[M] * (r - l + );
}
int main()
{
Sca2(N,M); Sca2(K,e);
init();
For(i,,e){
int u,v,w; Sca3(u,v,w);
add(u,v,w); add(v,u,w);
}
int q;Sca(q);
while(q--){
int x,l,r; Sca3(x,l,r);
For(i,l,r) use[x][i] = ;
}
for(int i = ; i <= M ; i ++)
for(int j = ; j <= N ; j ++)
use[i][j] += use[i][j - ];
for(int i = ; i <= N ; i ++)
for(int j = i; j <= N ; j ++)
cost[i][j] = Dijkstra(i,j);
Mem(dp,0x3f);
dp[] = ;
for(int i = ; i <= N; i ++){
for(int j = ; j <= i - ; j ++){
if(cost[j + ][i] == INF) continue;
dp[i] = min(dp[i],dp[j] + cost[j + ][i] + K);
}
}
Prl(dp[N] - K);
#ifdef VSCode
system("pause");
#endif
return ;
}