记录编号	37632	评测结果	AAAAAAAAAA
题目名称	运输公司	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.082 s
提交时间	2012-04-05 11:02:12	内存使用	0.28 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int oo=~0u>>2;

struct edge
{
	int t,cost;
	edge *next;
	edge(int _t,int _cost,edge *_next):t(_t),cost(_cost),next(_next){}
}*Map[110];

int f[110],N,M,K,E,D;
bool flag[110][110];

void addedge(int s,int t,int cost)
{
	Map[s]=new edge(t,cost,Map[s]);
	Map[t]=new edge(s,cost,Map[t]);
}

bool check(int x,int y,int k)
{
	for(int i=x;i<=y;i++)
		if(!flag[i][k])
			return false;
	return true;
}

int djs(int x,int y)
{
	priority_queue<pair<int,int> >heap;
	int dist[110];
	bool vis[110];
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=M;i++)
		dist[i]=oo;
	dist[1]=0;
	for(int i=2;i<M;i++)
		if(!check(x,y,i))
			vis[i]=true;
	heap.push(make_pair(0,1));
	while(!heap.empty())
	{
		int u=heap.top().second;
		heap.pop();
		if(!vis[u])
		{
			vis[u]=true;
			for(edge *p=Map[u];p;p=p->next)
			{
				int t=p->t,cost=p->cost;
				if(dist[t]>dist[u]+cost)
				{
					dist[t]=dist[u]+cost;
					heap.push(make_pair(-dist[t],t));
				}
			}
		}
	}
	return dist[M];
}

int main()
{
	freopen("transz.in","r",stdin);
	freopen("transz.out","w",stdout);
	scanf("%d%d%d%d",&N,&M,&K,&E);
	for(int i=1;i<=E;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c);
	}
	scanf("%d",&D);
	memset(flag,1,sizeof(flag));
	for(int i=1;i<=D;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		for(int j=b;j<=c;j++)
			flag[j][a]=false;
	}
	for(int i=1;i<=N;i++)
		f[i]=oo;
	f[0]=-K;
	for(int i=1;i<=N;i++)
		for(int j=0;j<i;j++)
		{
			int re=djs(j+1,i);
			if(re!=oo)
				f[i]=min(f[i],f[j]+re*(i-j)+K);
		}
	printf("%d\n",f[N]);
	return 0;
}