记录编号	77843	评测结果	AWWWWWWWWA
题目名称	运输公司	最终得分	20
用户昵称	Launcher	是否通过	未通过
代码语言	C++	运行时间	0.019 s
提交时间	2013-11-02 19:48:27	内存使用	0.47 MiB

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int n=0,m=0,e,p,l;
int a[30][30]={0};
int f[30][30]={0};
int g[10002][3]={0};
int r[100]={0};
int u[102][100]={0};
int ff(int x,int y)
{
	y++;
	if (r[x]!=0)
		u[l][y]=ff(r[x],y);
	else 
		return x;
	return x;
}
int main()
{
	freopen("transz.in","r",stdin);
	freopen("transz.out","w",stdout);
	int i,j,k,ans=0,h;
	cin>>n>>m>>e>>p;
	int fuck=0;
	int x,y;
	for (i=1;i<=m;i++)
	{
		for (j=1;j<=m;j++)
			a[i][j]=20000000;
	}
	for (i=1;i<=p;i++)
	{
		cin>>x>>y>>l;
		a[x][y]=l;
		a[y][x]=l;
	}

	int d,t;
	cin>>d;
	for (i=1;i<=d;i++)
		cin>>g[i][0]>>g[i][1]>>g[i][2];
	for (l=1;l<=n;l++)
	{
	for (i=1;i<=m;i++)
		r[i]=0;
	for (i=1;i<=m;i++)
	{
		for (j=1;j<=m;j++)
			f[i][j]=a[i][j];
	}

	for (i=1;i<=d;i++)
	{
		if ((g[i][1]<=l)&&(l<=g[i][2]))
		{
			t=g[i][0];
			for (p=1;p<=m;p++)
			{
				f[p][t]=200000000;
				f[t][p]=200000000;
			}
		}
	}
	r[m]=1;
	for (k=1;k<=m;k++)
		for (i=1;i<=m;i++)
			if (i!=k)
			for (j=1;j<=m;j++)
				if ((k!=j)&&(i!=j))
					if (f[i][j]>f[i][k]+f[k][j])
					{
						f[i][j]=f[i][k]+f[k][j];
						
						if ((i==1)&&(j==10))
						{	
							r[k]=i;
							r[j]=k;
						}
						//if (k==3)
						//	cout<<r[k]<<' '<<r[j]<<' '<<j<<endl;
					}
	
	u[l][1]=ff(r[m],1);
	fuck=0;
	for (i=1;i<=m;i++)
		if (u[l-1][i]!=u[l][i])
			fuck=1;
	//for (i=1;i<=m;i++)
	//	cout<<u[l][i]<<' ';
	//cout<<endl;
	ans+=f[1][m];
	if ((l>1)&&(fuck==1) )
		ans+=e;
	

	}
	cout<<ans<<endl;
	return 0;
}