【BZOJ1003】物流运输

  DP+最短路，DP选择需要修改路径的时间。然后时间复杂度几乎可以乱来的。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=110,maxm=30;
 
struct Graph
{
    int head[maxm],next[maxm*maxm],E[maxm*maxm],D[maxm*maxm],Ecnt;
    int Arr[maxm];
    int In[maxm];
    int Que[maxm];
    int Dis[maxm];
    int top,tail;
    int s,t;
 
    void Add_Edge(int x,int y,int d) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;D[Ecnt]=d;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;D[Ecnt]=d;}
 
    void Push_back(int x) {if (--top==-1) top=maxm-1;Que[top]=x;In[x]=1;}
    void Push_front(int x) {Que[tail++]=x;if (tail==maxm) tail=0;In[x]=1;}
    int Front() {return Que[top];}
    void Pop() {In[Que[top++]]=0;if (top==maxm) top=0;}
     
    void Spfa()
    {
        memset(Dis,0x7F,sizeof(Dis));
        memset(In,0,sizeof(In));
        Dis[s]=0;top=tail=0;
        Push_back(s);
        while (top!=tail)
        {
            int x=Front();Pop();
            for (int i=head[x];i;i=next[i]) if (Arr[E[i]])
                if (Dis[E[i]]>Dis[x]+D[i])
                {
                    Dis[E[i]]=Dis[x]+D[i];
                    if (!In[E[i]])
                        if (Dis[E[i]]<Dis[Front()]) Push_front(E[i]);
                        else Push_back(E[i]);
                }
        }
    }
 
    int Cost() {Spfa();return (Dis[t]!=0x7f7f7f7f)?Dis[t]:-1;}
}G;
 
int Arrivable[maxm][maxn];
int dis[maxn][maxn];
int f[maxn];
int n,m,K,e,d;
 
void Init()
{
    scanf("%d%d%d%d",&n,&m,&K,&e);
    for (int i=1;i<=e;i++)
    {
        int a,b,l;
        scanf("%d%d%d",&a,&b,&l);
        G.Add_Edge(a,b,l);
    }
    G.s=1;G.t=m;
    scanf("%d",&d);
    for (int i=1;i<=m;i++)
    for (int j=1;j<=n;j++)
        Arrivable[i][j]=1;
    for (int i=1;i<=d;i++)
    {
        int P,a,b;
        scanf("%d%d%d",&P,&a,&b);
        for (int i=a;i<=b;i++) Arrivable[P][i]=0;
    }
}
 
void Dis_Init()
{
    for (int i=1;i<=n;i++)
    {
        for (int k=1;k<=m;k++) G.Arr[k]=1;
        for (int j=i;j<=n;j++)
        {
            for (int k=1;k<=m;k++) G.Arr[k]&=Arrivable[k][j];
            dis[i][j]=G.Cost();
        }
    }
}
 
void DP()
{
    memset(f,0x7f,sizeof(f));
    f[0]=0;
    for (int i=1;i<=n;i++) if (dis[1][i]!=-1) f[i]=dis[1][i]*i;
    for (int i=2;i<=n;i++)
    for (int j=1;j<i;j++)
    if (dis[j+1][i]!=-1) f[i]=min(f[i],f[j]+dis[j+1][i]*(i-j)+K);
}
 
void Print() {printf("%d\n",f[n]);}
 
int main()
{
    Init();
    Dis_Init();
    DP();
    Print();
    return 0;
}