首页 > 代码库 > BZOJ 1003 物流运输trans（最短路）

BZOJ 1003 物流运输trans（最短路）

2024-07-09 00:14:15   217人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1003

思路：m个点e条边n天。给出每条边的权值以及有些点有些天不能走。对于某连续的两天i和i+1，若两天从起点到终点选择的路径不同需要额外代价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;}

 

 

 


联系
我们