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;
}