Eva

Time Limit: 10 Sec  Memory Limit: 162 MB

Description

　　物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转
停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种
因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是
修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本
尽可能地小。

　　第一行是四个整数n（1<=n<=100）、m（1<=m<=20）、K和e。n表示货物运输所需天数，m表示码头总数，K表示
每次修改运输路线所需成本。接下来e行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编
号以及航线长度（>0）。其中码头A编号为1，码头B编号为m。单位长度的运输费用为1。航线是双向的。再接下来
一行是一个整数d，后面的d行每行是三个整数P（ 1 < P < m）、a、b（1< = a < = b < = n）。表示编号为P的码
头从第a天到第b天无法装卸货物（含头尾）。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一
条从码头A到码头B的运输路线。

　　包括了一个整数表示最小的总成本。总成本=n天运输路线长度之和+K*改变运输路线的次数。

5 5 10 8
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1             
3 3 3
4 4 5

32
//前三天走1-4-5，后两天走1-3-5，这样总成本为(2+2)*3+(3+2)*

/**************************************************************

    Problem: 1003

    User: ictsing

    Language: C++

    Result: Accepted

    Time:272 ms

    Memory:1400 kb

****************************************************************/

 

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,m,k,e;

inline int read()

{

  int num=0,flag=1;

  char ch;

  do{

    ch=getchar();

    if(ch=='-') flag=-1;

  }while(ch<'0'||ch>'9');

  do{

    num=num*10+ch-'0';

    ch=getchar();

  }while(ch>='0'&&ch<='9');

  return num*flag;

}

const int sta=100+5;

const int days=20+2;

bool flag[days][sta],can[sta],vis[sta];

int dis[sta];

const int mt=10000+5;

int q[mt];

const int edgem=1000+5;

int head[sta],cnt=0;

int to[edgem<<1],nxt[edgem<<1],w[edgem<<1];

void adde(int uu,int vv,int ww)

{

    cnt++,to[cnt]=vv,nxt[cnt]=head[uu],w[cnt]=ww,head[uu]=cnt;

}

int sum[sta][sta],f[days];

const int inf=0x3f3f3f3f;

int spfa(int l,int r)

{

    memset(vis,0,sizeof(vis));

    memset(dis,0,sizeof(dis));

    memset(can,1,sizeof(can));

    memset(q,0,sizeof(q));

    for(int i=1;i<=m;i++)

        for(int j=l;j<=r;j++)

           if(flag[i][j]) can[i]=0;

 

    int he=0,ta=1;q[ta]=1,vis[1]=1;

    while(he<ta)

    {

        int u=q[++he];vis[u]=0;

        for(int i=head[u];i;i=nxt[i])

        {

            int v=to[i];

            if((dis[v]==0||dis[u]+w[i]<dis[v])&&can[v])

            {

                dis[v]=dis[u]+w[i];

                if(!vis[v]) vis[v]=1,q[++ta]=v;

            }

        }

    }

    return (r-l+1)*dis[m];

}

int main()

{

    n=read(),m=read(),k=read(),e=read();

    int uu,vv,ww;

    for(int i=1;i<=e;i++)

        uu=read(),vv=read(),ww=read(),adde(uu,vv,ww),adde(vv,uu,ww);

    int d=read(),p,a,b;

    memset(flag,0,sizeof(flag));

    for(int i=1;i<=d;i++)

    {

       p=read(),a=read(),b=read();

       for(int j=a;j<=b;j++) flag[p][j]=1;

    }

    for(int l=1;l<=n;l++)

        for(int r=1;r<=n;r++)

          sum[l][r]=spfa(l,r);

    for(int i=1;i<=n;i++)

    {

        f[i]=sum[1][i];

        if(f[i]==0) f[i]=1000000000;//int 被爆

        for(int j=0;j<i;j++)

            if(sum[j+1][i])//又是dp的边界问题，wc调了半个多个小时

            f[i]=min(f[i],f[j]+k+sum[j+1][i]);

    }

    printf("%d\n",f[n]);

    return 0;

}