BZOJ 1003物流輸送trans(最短)

タイトルリンク:http://61.187.179.132/JudgeOnline/problem.php?id=1003
構想:m個の点e辺n日.各エッジの重みを与え、一部の日は歩けないことがあります.ある連続する2日間iおよびi+1について、2日間の始点から終点までの選択経路が異なる場合、追加の代価Kが必要となる.最小の総代価を求めます:ans=sum(毎日の代価)+K*の変化の回数.毎日の代価は、この日sからtまで選択されたパスの長さとして定義される.
構想:cost[i][j]はi日目からj日目までの経路の最短経路を選択し、f[i]は前i日の総代価を表し、f[i]=min(f[j]+cost[j+1][i]*(i-j)+K)となる.計算cost[i][j]はiとjを直接列挙して最短回路を計算する.ここには[i,j]日が歩けないかもしれないし、[p,q]日も歩けないかもしれない.しばらくしか歩けないというわけではありません.最短ルートを求めるたびに歩ける点しか利用できません.
 

vector<pair<int,int> > g[N];

int n,m,K,e,d;

int node[N],L[N],R[N];

int ok[N];





int cal(int x,int y)

{

    queue<int> Q;

    int dis[N],h[N],i,u,v,w;

    clr(ok,0);

    FOR0(i,d)

    {

        u=node[i];

        if(x>R[i]||y<L[i]);

        else ok[u]=1;

    }

    FOR1(i,m) dis[i]=INF;

    clr(h,0); dis[1]=0; Q.push(1);

    while(!Q.empty())

    {

        u=Q.front();

        Q.pop();





        h[u]=0;

        FOR0(i,SZ(g[u]))

        {

            v=g[u][i].first;

            w=g[u][i].second;

            if(!ok[v]&&dis[v]>dis[u]+w)

            {

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

                if(!h[v]) Q.push(v),h[v]=1;

            }

        }

    }

    return dis[m];

}





int f[N],cost[N][N];





int main()

{

    RD(n,m); RD(K,e); clr(L,-1);

    int i,j,u,v,w;

    FOR0(i,e)

    {

        RD(u,v,w);

        g[u].pb(MP(v,w));

        g[v].pb(MP(u,w));

    }

    RD(d);

    FOR0(i,d) RD(node[i],L[i],R[i]);

    FOR1(i,n) for(j=i;j<=n;j++) cost[i][j]=cal(i,j);

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

    {

        f[i]=INF;

        for(j=0;j<i;j++) if(f[j]!=INF&&cost[j+1][i]!=INF)

        {

            if(j==0) w=0;

            else w=K;

            f[i]=min(f[i],f[j]+cost[j+1][i]*(i-j)+w);

        }

    }

    PR(f[n]);

    return 0;

}