记录编号	437485	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2006] 物流运输	最终得分	100
用户昵称	Hzoi_moyi	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2017-08-14 10:46:44	内存使用	0.60 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int f[105],n,m,k,e,h[25],e1,a1,a2,a3;
int d,di[25],date[25][105],dis[105][105];
bool r[25];
queue<int> q;
struct B
{
    int ne,v,w;
}b[20000];
void add(int x,int y,int z)
{
    b[e1].v=y;
    b[e1].w=z;
    b[e1].ne=h[x];
    h[x]=e1++;
}
void spfa(int l,int ri)
{
     for(int i=1;i<=m;i++) di[i]=10000000;
     q.push(1);
     di[1]=0;
     r[1]=1;
     while(!q.empty())
     {
        a2=q.front();
        r[a2]=0;
        q.pop();
        for(int i=h[a2];i!=-1;i=b[i].ne)
          if(date[b[i].v][ri]-date[b[i].v][l-1]==0&&di[b[i].v]>di[a2]+b[i].w)
          {
             di[b[i].v]=di[a2]+b[i].w;
             if(!r[b[i].v])
             {
                 r[b[i].v]=1;
                 q.push(b[i].v);
             }
          }
     }
     dis[l][ri]=di[m];
}
inline void bj(int &x,int y)
{
     x=x<y?x:y;
}
int main()
{
    //freopen("t.txt","r",stdin);
    freopen("bzoj_1003.in","r",stdin);
    freopen("bzoj_1003.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&k,&e);
    memset(h,-1,sizeof(h));
    for(int i=1;i<=e;i++)
    {
       scanf("%d%d%d",&a1,&a2,&a3);
       add(a1,a2,a3);
       add(a2,a1,a3);
    }
    scanf("%d",&d);
    for(int i=1;i<=d;i++)
    {
       scanf("%d%d%d",&a1,&a2,&a3);
       for(int j=a2;j<=a3;j++)
          date[a1][j]++;
    }
    for(int i=1;i<=m;i++)
      for(int j=1;j<=n;j++)
       date[i][j]+=date[i][j-1];
    for(int i=1;i<=n;i++)
      for(int j=i;j<=n;j++)
        spfa(i,j);
    memset(f,0x3f,sizeof(f));
    f[1]=dis[1][1];
    f[0]=0;
    for(int i=2;i<=n;i++)
    {
      f[i]=(long long)dis[1][i]*i;
      for(int j=1;j<=i;j++)
        bj(f[i],f[j-1]+dis[j][i]*(i-j+1)+k);
    }
    printf("%d",f[n]);  
    //while(1);
    return 0;
}