codevs1403(dp+克鲁斯卡尔)

判断是否处于灾害期那个地方，思路错了一下午，否则我的prim的做法虽然慢，但是就应该还可以过上7个点，结果wa了那么多

因为一个边的灾害期不一定就一次，我的做法虽然可以保证一次，但是多次无法处理

导致我还以为我 的prim错了呢，

不过练了对拍和代码能力

和bzoj那个套最短路的一个样

对了，一定要注意细节，不要以为他不会卡你细节！！！！，也许就是这细节决定你的成败，永远不要有侥幸心理！！

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
const int inf=0x3f3f3f3f;

struct aa
{
	int x,y,w,t1,t2;
	bool operator <(const aa &b)const
	{
		return w<b.w; 
	}
}edge[5009];

int n,m,t,v,k;
int id[309][309],val[59][59];
int dp[59],fa[5009];
int cr[59][309][309];
int find(int x)
{
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
bool pd(int a,int b,int x,int y)
{
    for(int i=a;i<=b;i++)
        if(cr[i][x][y])return 0;
    return 1;
}
int work(int x,int y)
{
	for (int i=1;i<=n;i++) fa[i]=i;
	int j=0,ans=0;	
	for (int i=1;i<=m;i++) 
	if (pd(x,y,edge[i].x,edge[i].y))
	{
		int fx=find(edge[i].x),fy=find(edge[i].y);
		if (fx!=fy)
		{
			j++;
			ans+=edge[i].w;
			fa[fx]=fy;
			if (j==n-1) return ans;
		}
	}
	return inf;
}
int main()
{
	scanf("%d%d%d%d%d",&n,&m,&t,&v,&k);
	int x,y,z;
	for (int i=1;i<=m;i++) 
	{
		scanf("%d%d%d",&x,&y,&z);
		if (x>y)swap(x,y);
		edge[i].x=x;edge[i].y=y;edge[i].w=z;id[x][y]=i;
	}
	int p,t1,t2;
	scanf("%d",&p);
	for (int i=1;i<=p;i++)
	{
		scanf("%d%d%d%d",&x,&y,&t1,&t2);
		if (x>y) swap(x,y);if (t1>t2) swap(t1,t2);
		for(int j=t1;j<=t2;j++)cr[j][x][y]=1;
	}
	sort(edge+1,edge+m+1);
	for (int i=1;i<=t;i++)
		for (int j=i;j<=t;j++) val[i][j]=work(i,j);
	for (int i=1;i<=t;i++)
	{
		dp[i]=inf;
		for (int j=0;j<i;j++) if (val[j+1][i]!=inf) 
		dp[i]=min(dp[i],dp[j]+val[j+1][i]*v*(i-j)+k);
	}	
	printf("%d",dp[t]);
	return 0;
}