洛谷P1772 [ZJOI2006]物流运输题解-白红宇

洛谷P1772 [ZJOI2006]物流运输题解

阅读量：4916 次

发布时间：2019-06-11

本文共 2586 字，大约阅读时间需要 8 分钟。

题目描述

物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是修改路线是—件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本尽可能地小。

输入输出格式

输入格式：

第一行是四个整数n(l≤n≤100)、m(l≤m≤20)、K和e。n表示货物运输所需天数，m表示码头总数，K表示每次修改运输路线所需成本。接下来e行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编号以及航线长度(>0)。其中码头A编号为1，码头B编号为m。单位长度的运输费用为1。航线是双向的。再接下来一行是一个整数d，后面的d行每行是三个整数P(1<P<m)，a，b(1≤a≤b≤n)。表示编号为P的码头从第a天到第b天无法装卸货物（含头尾）。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一条从码头A到码头B的运输路线。

输出格式：

包括了一个整数表示最小的总成本。总成本=n天运输路线长度之和+K*改变运输路线的次数。

输入输出样例

输入样例#1：

5 5 10 8  1 2 1  1 3 3  1 4 2  2 3 2  2 4 4  3 4 1  3 5 2  4 5 2  4  2 2 3  3 1 1  3 3 3  4 4 5

输出样例#1：

说明

【样例输入说明】

上图依次表示第1至第5天的情况，阴影表示不可用的码头。

【样例输出说明】

前三天走1-4-5，后两天走1-3-5，这样总成本为(2+2)*3+(3+2)*2+10=32。

_NOI导刊2010提高（01）

————————————————我是分割线——————————————

最短路+dp 好题

预处理每天的最短路，再dp选择。

可以用f[i]表示到第i天的时候最小费用，那么f[i]={f[j]+cost[j+1,i]+K}(0<=j<i)，其中cost[i,j]表示由第i天到第j天都可以走得通的最短路。

这样求完之后再减去一个多余的K即可。（当然你也可以在预处理时做手脚）

1 /*  2     Problem:  3     OJ:  4     User:    S.B.S.  5     Time:  6     Memory:  7     Length:  8 */  9 #include
      
        10 #include
       
         11 #include
        
          12 #include
         
           13 #include
          
            14 #include
           
             15 #include
            
              16 #include
             
               17 #include
              
                18 #include
               
                 19 #include
                
                  20 #include
                 
                   21 #include
                  
                    22 #include
                   
                     23 #include
                     24 #define F(i,j,k) for(int i=j;i
                     
                      =k;i--) 27 #define maxn 1001 28 #define inf 0x3f3f3f3f 29 #define maxm 1001 30 #define mod 998244353 31 //#define LOCAL 32 using namespace std; 33 int read(){ 34 int x=0,f=1;char ch=getchar(); 35 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} 36 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 37 return x*f; 38 } 39 int n,m; 40 int k,e,dd; 41 int mp[maxn][maxn],h[maxn][maxn],a[maxn][maxn]; 42 int d[maxn]; 43 int dp[maxn],q[maxn]; 44 bool vis[maxn]; 45 inline void init() 46 { 47 M(mp,0);int x,y,z; 48 F(i,0,e){ 49 cin>>x>>y>>z; 50 if(mp[x][y]==0||mp[x][y]>z) mp[x][y]=mp[y][x]=z; 51 } 52 M(h,0); 53 cin>>dd; 54 F(i,0,dd){ 55 cin>>x>>y>>z; 56 for(int j=y;j<=z;j++) h[x][j]=1; 57 } 58 for(int i=1;i<=m;i++) 59 { 60 a[i][0]=0; 61 for(int j=1;j<=n;j++) a[i][j]=a[i][j-1]+h[i][j]; 62 } 63 } 64 inline int spfa(int u,int v) 65 { 66 int hd,tl; 67 hd=tl=0; 68 M(d,0x3f);M(vis,0); 69 q[tl++]=1;d[1]=0; 70 while(hd!=tl){ 71 int i=q[hd++]; 72 vis[i]=0; 73 for(int j=1;j<=m;j++) 74 { 75 if(mp[i][j]&&a[j][v]-a[j][u]==0&&d[i]+mp[i][j]
                      
                       >n>>m>>k>>e){106 init();107 solve();108 }109 return 0;110 }

p1772

转载于:https://www.cnblogs.com/SBSOI/p/5913182.html

你可能感兴趣的文章