记录编号	77813	评测结果	AAAAAAAAAA
题目名称	运输公司	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2013-11-02 18:23:34	内存使用	0.56 MiB

#include<stdio.h>
#include<vector>

#define int long long
//#define %d %lld
using std::vector;

const int MAXM=20+5;
const int MAXN=100+5;
int n,m,K,e;

struct not_open_day{
	int be;
	int en;
	not_open_day(int a,int b){be=a;en=b;}
};

struct road_{
	int u,v;
	int cost;
}road[MAXN*MAXN];

struct matou_{
	vector<not_open_day> not_open;
	vector<int> r;
}matou[MAXM];

struct queue{
	int q[MAXN*MAXM];
	int h,t;
	queue(){h=t=0;}
	int inc(int &i){int t=i;i++;i%(MAXN*MAXM);return t;}
	bool empty(){return h>=t;}
	void push(int i){q[inc(t)]=i;}
	int front(){return q[inc(h)];}
};

void read(){
	scanf("%lld %lld %lld %lld",&n,&m,&K,&e);
	for(int i=1;i<=e;i++){
		road_ &ro=road[i];
		scanf("%lld %lld %lld",&ro.u,&ro.v,&ro.cost);
		matou[ro.u].r.push_back(i);
		matou[ro.v].r.push_back(i);
	}
	int d,p,a,b;
	scanf("%lld",&d);
	for(int i=1;i<=d;i++){
		scanf("%lld %lld %lld",&p,&a,&b);
		matou[p].not_open.push_back(not_open_day(a,b));
	}
}

bool jiao(int a,int b,int p,int q){
	if(b<p)return false;
	if(a>q)return false;
	return true;
}

void get_is_open(int a,int b,bool *is_open){
	for(int i=2;i<m;i++){
		int t=matou[i].not_open.size();
		is_open[i]=true;
		for(int j=0;j<t;j++){
			not_open_day &t_n=matou[i].not_open[j];
			if(jiao(a,b,t_n.be,t_n.en)){
				is_open[i]=false;
				break;
			}
		}
	}
	is_open[m]=true;
}

int spfa(int a,int b){
	int d[MAXM]={0};
	bool inq[MAXM]={0};
	bool is_open[MAXM]={0};
	queue q;
	get_is_open( a, b,is_open);
	inq[1]=true;
	q.push(1);
	while(!q.empty()){
		int x=q.front();
		inq[x]=false;
		matou_ &ma=matou[x];
		int t=ma.r.size();
		for(int i=0;i<t;i++){
			road_ &ro=road[ma.r[i]];
			int v= ro.u==x?ro.v:ro.u;
			if(is_open[v] && (!d[v] || d[v]>d[x]+ro.cost)){
				d[v]=d[x]+ro.cost;
				if(!inq[v])q.push(v);
			}
		}
	}
	return d[m]?d[m]:99999999;
}

inline int min(int a,int b){return a>b?b:a;}

int solve(){
	int f[MAXN]={0};
	f[0]=(-1)*K;
	for(int i=1;i<=n;i++){
		int ans=99999999;
		for(int j=1;j<=i;j++){
			ans=min(ans,f[j-1]+K+(i-j+1)*spfa(j,i));
		}
		f[i]=ans;
	}
	return f[n];
}

void open(){
	freopen("transz.in","r",stdin);
	freopen("transz.out","w",stdout);
}

 main(){
	open();
	//printf("test\n");
	read();
	int ans=solve();
	printf("%lld",ans);
	//close();
	return 0;
}