记录编号	77873	评测结果	AAAAAAAAAA
题目名称	运输公司	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2013-11-02 20:23:29	内存使用	0.33 MiB

#include<fstream>
#include<cmath>
#include<cstring>
#include<vector>
#include<deque>
#include<algorithm>
using namespace std;
ifstream fi("transz.in");
ofstream fo("transz.out");
const int INF=0x7FFFFFFF;
int K,E,N,M,D,f[101],key[101];
bool inq[101];
vector <int> p[101],val[101];
bool boo[101][101];
bool Unable(int P,int a,int b)
{
	for(int i=a;i<=b;i++)
		if(boo[P][i])return false;
	return true;
}
int SPFA(int daystart,int dayend)
{
	for(int i=1;i<=M;i++)inq[i]=0;
	for(int i=1;i<=M;i++)
		if(!Unable(i,daystart,dayend))inq[i]=1;
	for(int i=2;i<=M;i++)key[i]=INF;
	inq[1]=1; key[1]=0;
	deque <int> q;
	q.push_back(1);
	int u,v,d;
	while(!q.empty())
	{
		u=q.front();
		q.pop_front();
		inq[u]=0;
		for(unsigned int i=0;i<p[u].size();i++)
		{
			v=p[u][i];
			d=val[u][i];
			if(key[v]>key[u]+d)
			{
				key[v]=key[u]+d;
				if(!inq[v])
				{
					inq[v]=1;
					q.push_back(v);
				}
			}
		}
	}
	return key[M];
}
int main()
{
	fi>>N>>M>>K>>E;
	memset(boo,0,sizeof(boo));
	int a,b,c;
	while(E--)
	{
		fi>>a>>b>>c;
		p[a].push_back(b);val[a].push_back(c);
		p[b].push_back(a);val[b].push_back(c);
	}
	fi>>D;
	while(D--)
	{
		fi>>c>>a>>b;
		for(int i=a;i<=b;i++)
			boo[c][i]=1;
	}
	f[0]=0;
	for(int i=1;i<=N;i++)
	{
		f[i]=INF;
		for(int j=0;j<i;j++)
		{
			c=SPFA(j+1,i);
			if(c==INF)continue;
			f[i]=min(f[i],f[j]+c*(i-j)+K);
		}
	}
	fo<<f[N]-K<<endl;
	return 0;
}