记录编号	437542	评测结果	AAAAATATAT
题目名称	[ZJOI 2006] 物流运输	最终得分	70
用户昵称	天亮说晚安·	是否通过	未通过
代码语言	C++	运行时间	6.668 s
提交时间	2017-08-14 11:29:10	内存使用	34.62 MiB

#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 105
#define inf 1061109567
using namespace std;

inline int read(){
    char x=getchar();int sum=0,f=1;
    while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
    while(x>='0'&&x<='9'){sum=sum*10+x-'0';x=getchar();}
    return f*sum;
}

int n,m,k,e; bool biao[105][25];
int zhuang[2000000],cnt,st[2000000],cost[2000000];
int f[2][2000000],to[25],a[25][25],now;
int dis[25],b[25];
int dui[25],h,t;

inline int judge(int tai){
	 if(!(tai&to[1])) return inf;
	 memset(dis,0x3f,sizeof(dis));memset(b,0,sizeof(b));
	 memset(dui,0,sizeof(dui));
     h=1,t=0;
	 dui[++t]=1;  b[1]=1; dis[1]=0;
     while(h<=t){
	     int r=dui[h++];  b[r]=0;
	     for(int i=2;i<=m;i++){
		    if(!a[i][r]||!(tai&to[i])) continue;
		    if(dis[i]>dis[r]+a[i][r]){
			   dis[i]=dis[r]+a[i][r];
			   if(!b[i]){dui[++t]=i, b[i]=1;}
			}
		 }
	 }
	 return dis[m];
}

void init(){
	 int all=(1<<m)-1;
     for(int i=0;i<m;i++){  
	    st[1<<i]=m-i; 
        to[m-i]=1<<i;
	 }
	 for(int i=1;i<=all;i++){
	     int x=judge(i);
	     if(x==inf) continue;
	     zhuang[++cnt]=i,cost[cnt]=x;
	 }
}

inline int lowbit(int x){return x&(-x);}

void dp(){
     now=0;  int minn1=0,minn2=0,xixi1=inf,xixi2=inf;
     for(int i=1;i<=n;i++){
	    for(int j=1;j<=cnt;j++){
	    	f[now][j]=inf;
		    bool qq=0;
			for(int q=zhuang[j];q;q-=lowbit(q))
	           if(biao[i][st[lowbit(q)]]){qq=1;break;}
		    if(qq) continue;
		    int tmp=f[now^1][j],xiao=inf;
			f[now][j]=f[now^1][j]+cost[j];
			
		    if(tmp==minn1) xiao=minn2;
		    else           xiao=minn1;
		    f[now][j]=min(f[now][j],xiao+cost[j]+k);
		    if(f[now][j]<xixi1) xixi2=xixi1,xixi1=f[now][j];
		    else if(f[now][j]<xixi2)  xixi2=f[now][j];
		}
		minn1=xixi1,minn2=xixi2; xixi1=inf,xixi2=inf;
		now^=1;
	}
	now^=1;
}

int main(){
freopen("bzoj_1003.in","r",stdin);
freopen("bzoj_1003.out","w",stdout);
     n=read(),m=read(),k=read(),e=read();
	 for(int i=1;i<=e;i++){
	     int x=read(),y=read(),z=read();
	     a[x][y]=a[y][x]=z;
     }
	 int q=read();
	 for(int i=1;i<=q;i++){
	    int x=read(),y=read(),z=read();
	    for(int j=y;j<=z;j++) biao[j][x]=1;
	 } 
	 init();
	 dp();
	 int ans=inf;
	 for(int i=1;i<=cnt;i++)  ans=min(ans,f[now][i]);
     printf("%d",ans);
}