BZOJ1003: [ZJOI2006]物流运输

水深无声 2023-06-04 08:00 25阅读 0赞

[**题目链接**][Link 1]

**发现如果没有限制的话，就是最短路的模板题。但是这道题的关键就是要处理题上的限制。我们就可以用一个数组来存哪一天哪个港口不能走，跑最短路的时候特判一下，dijkstra处理出所有天的最短路径。**

**由于数据范围n<=100，所以n^2\*（elogm）的时间复杂度也随便能跑。**

**接下来又怎么办呢？就可以考虑dp，看了题解发现dp的思路还是比较简单的。考虑如何设计状态，dp\[i\]表示在第i天的最小费用，而我们还要枚举j，也就是在第i天之前是否改变了路径。**

**可以得出转移方程dp\[i\]=min(dp\[i\],dp\[j\]+k+(i-j)\*cost\[j+1\]\[i\])**

**代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<queue>
    #include<cstring>
    using namespace std;
    const int maxn=1025;
    const int N=550;
    priority_queue< pair<long long,int> > q;
    long long dis[maxn];
    struct node{
        int nxt,to,val;
    }edge[maxn*3];
    bool vis[maxn];
    int head[maxn],cnt;
    int x,y,v;
    void add(int x,int y,int v){
        edge[++cnt].nxt=head[x];
        edge[cnt].to=y;
        edge[cnt].val=v;
        head[x]=cnt;
    }
    int used[N][N]; 
    int lock[maxn];
    int cost[N][N];
    long long dp[maxn];
    long long min(long long a,long long b){
        return a>b?b:a;
    }
    int n,m,k,e;
    int d,p,a,b;
    long long dijkstra(int x,int y){
        memset(vis,false,sizeof(vis));
        memset(dis,88,sizeof(dis));
        memset(lock,false,sizeof(lock));
        for(int i=1;i<=m;i++){
            for(int j=x;j<=y;j++) if(used[i][j]) lock[i]=true;
        }
        dis[1]=0;
        q.push(make_pair(0,1));
        while(!q.empty()){
            int u=q.top().second;
            q.pop();
            if(vis[u]) continue;
            vis[u]=true;
            for(int i=head[u];i;i=edge[i].nxt){
                int v=edge[i].to;
                if(dis[v]>dis[u]+edge[i].val&&(!lock[v])){
                    dis[v]=dis[u]+edge[i].val;
                    q.push(make_pair(-dis[v],v));
                }
            }
        }
        return dis[m];
    }
    int main(){
        scanf("%d%d%d%d",&n,&m,&k,&e);
        for(int i=1;i<=e;i++){
            scanf("%d%d%d",&x,&y,&v);
            add(x,y,v);add(y,x,v);
        }
        scanf("%d",&d);
        for(int i=1;i<=d;i++){
            scanf("%d%d%d",&p,&a,&b);
            for(int j=a;j<=b;j++) used[p][j]=1;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) cost[i][j]=dijkstra(i,j);
        } 
        for(int i=1;i<=n;i++){
            dp[i]=(long long)i*cost[1][i];
            for(int j=1;j<=i;j++){
         //在第j天更换 
                dp[i]=min(dp[i],dp[j]+k+(long long)(i-j)*cost[j+1][i]); 
            }
        }
        printf("%lld\n",dp[n]);
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11502486.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=1003
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/a1c6a2f2e0224d17a5648517cbc266a5.png