记录编号	38083	评测结果	AAAAAAAAAA
题目名称	运输公司	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2012-04-12 12:45:51	内存使用	0.35 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
#define MAXN 101
#define MAXM 21
#define pb(i) push_back(i)
#define read scanf
#define write printf
#define loop(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int INF=~0u>>2;
int N,M,K,E,D,F[MAXN];
bool Flag[MAXN][MAXM];
int Cost[MAXN][MAXN];
vector<int> Map[MAXM];
vector<int> Val[MAXM];

void init()
{
	read("%d %d %d %d\n",&N,&M,&K,&E);
	memset(Flag,0,sizeof(Flag));
	int a,b,c;loop(i,1,E) 
	{
		read("%d %d %d\n",&a,&b,&c); 
		Map[a].pb(b);  Val[a].pb(c);
		Map[b].pb(a);  Val[b].pb(c);
	}	read("%d\n",&D); loop(i,1,D)
	{
		read("%d %d %d\n",&a,&b,&c);
		loop(j,b,c) Flag[j][a]=1;
	}
}

bool check(int l,int r,int p)
{
	loop(i,l,r) if(Flag[i][p]) return false; return true;
}

int SPFA(int l,int r)
{
    int dist[MAXM],flag[MAXM];
    loop(i,1,M) dist[i]=INF,flag[i]=0;
    loop(i,1,M) if(!check(l,r,i)) flag[i]=1;
    queue<int> Q;
    int u,v; Q.push(1); dist[1]=0; flag[1]=1;
    int cost,newdist;
    while(!Q.empty())
    {
        u=Q.front(); Q.pop(); cost=dist[u]; flag[u]=0;
        for(unsigned int i=0;i<Map[u].size();i++)
        {
            v=Map[u][i];
            newdist=Val[u][i]+cost;
            if(dist[v]>newdist)
            {
                dist[v]=newdist;
                if(!flag[v]) Q.push(v),flag[v]=1;
            }
        }
    }
    return dist[M];
}

inline int Min(int a,int b) {return a<b?a:b;}

void dp()
{
	F[0]=0;
	loop(i,1,N)
	{
		F[i]=INF;
		for(int j=0;j<=i-1;j++)
		{
			int c=SPFA(j+1,i);
			if(c==INF) continue;
			F[i]=Min(F[i],F[j]+c*(i-j)+K);
		}
	}
	write("%d\n",F[N]-K);
}

int main()
{
	freopen("transz.in","r",stdin);
	freopen("transz.out","w",stdout);
	init();
	dp();
	return 0;
}