记录编号	140754	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2006] 物流运输	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2014-11-24 20:56:38	内存使用	0.41 MiB

#include <iostream>
#include <cctype>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
inline void getd(int &x){
	char c = getchar();
	bool minus = 0;
	while(!isdigit(c) && c != '-')c = getchar();
	if(c == '-')minus = 1, c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 + c - '0';
	if(minus)x = -x;
}
/*======================================================*/
const int maxn = 102, maxm = 21, INF = 0x3f3f3f3f;

struct event{int T, num; } E[2002];
inline bool operator < (const event &a, const event &b){
	return a.T < b.T;
}

int n, m, K, Ecnt = 0;
int inval[maxn][maxn] = {0}, cost[maxn][maxn], dp[maxn];

struct edge{
	int to, w;
	edge(int t, int c):to(t), w(c){}
};
vector<edge> adj[maxm];

queue<int> Q;
bool inQ[maxm] = {0};
int dis[maxm] = {0};
inline void setinf(){
	dis[1] = 0;
	for(int i = 2;i <= m;++i)
		dis[i] = INF;
}

inline void pushQ(int x){
	vector<edge>::iterator it;
	for(int i=1, j=2;i <= m;++i, j <<= 1)
		if(x & j){
			if(!inQ[i])Q.push(i), inQ[i] = 1;
			for(it = adj[i].begin();it != adj[i].end();++it)
				if(!inQ[it->to])Q.push(it->to), inQ[it->to] = 1;
		}
}

inline int spfa(int l, int r){
	vector<edge>::iterator it;
	int t;
	while(!Q.empty()){
		t = Q.front(); Q.pop(); inQ[t] = 0;
		for(it = adj[t].begin();it != adj[t].end();++it)
			if((!(inval[l][r] & (1 << it->to))) && dis[it->to] > dis[t] + it->w){
				dis[it->to] = dis[t] + it->w;
				if(!inQ[it->to])
					Q.push(it->to), inQ[it->to] = 1;
			}
	}
	return dis[m];
}

inline void init(){
	int i, j, e, k, d;
	getd(n), getd(m), getd(K), getd(e);
	while(e--){
		getd(i), getd(j), getd(k);
		adj[i].push_back(edge(j, k));
		adj[j].push_back(edge(i, k));
	}
	getd(d);
	while(d--){
		getd(k), getd(i), getd(j);
		E[Ecnt].T = i, E[Ecnt].num = k; ++Ecnt;
		E[Ecnt].T = j+1, E[Ecnt].num = k; ++Ecnt;
	}
	sort(E, E + Ecnt);
	for(j = 0, i = 1;i <= n;++i){
		inval[i][i] = inval[i-1][i-1];
		while(j < Ecnt && E[j].T == i){
			inval[i][i] ^= (1 << E[j].num);
			++j;
		}
	}
	for(i = 1;i < n;++i)
		for(j = i+1;j <= n;++j)
			inval[i][j] = inval[i][j-1] | inval[j][j];
	for(i = 1;i <= n;++i){
		setinf();
		Q.push(1), inQ[1] = 1;
		cost[i][n] = spfa(i, n);
		for(j = n-1;j >= i;--j){
			if(inval[i][j] == inval[i][j+1]){
				cost[i][j] = cost[i][j+1];
				continue;
			}
			pushQ(inval[i][j] ^ inval[i][j+1]);
			if(!inQ[1])Q.push(1), inQ[1] = 1;
			cost[i][j] = spfa(i, j);
		}
	}
	
}

inline void work(){
	int i, j, c;
	for(i = 1;i <= n;++i)
		dp[i] = cost[1][i] == INF ? INF : cost[1][i] * i;
	for(i = 2;i <= n;++i) for(j = 1;j < i;++j){
		if(cost[j+1][i] == INF)continue;
		c = dp[j] + cost[j+1][i] * (i - j) + K;
		if(c < dp[i])
			dp[i] = c;
	}
	printf("%d\n", dp[n]);
}

int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	#else
	freopen("bzoj_1003.in", "r", stdin);
	freopen("bzoj_1003.out", "w", stdout);
	#endif
	init();
	
	work();
	
	#if defined DEBUG
	cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
	#endif
	return 0;
}