P1772 [ZJOI2006]物流运输

题目描述

物流公司要把一批货物从码头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：

输出样例#1：

说明

【样例输入说明】

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

【样例输出说明】

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

_NOI导刊2010提高（01）

分析

开始思路错了QAQ，只要搜出每一天的最短路，及每一天是否改变，加起来。错误之处在于有时候可以不走最短路，如果上次改变了路线花了100，这次发现了最短路，比上次短10，那我们宁可不走最短路，走稍微长点的，我认为的一个坑点！！！

正解：套一个dp

预处理出cost[i][j]=从第i天到第j天不更换方案的最短路，然后f[i]表示前i天最少的总成本

状态转移方程：f[i]=min(f[i],f[j]+cost[j+1][i]+k);

code

40分代码

 1 #include<cstdio>
 2 #include<queue>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 const int MAXN = 30;
 7 struct Edge{
 8     int to,w,nxt;    
 9 }e[1010];
10 int dis[MAXN],pre[110][MAXN],head[MAXN];
11 bool pd[110][MAXN],vis[MAXN];
12 int d,n,m,k,t,ans,cnt;
13 queue<int>q;
14 
15 void add(int u,int v,int w)
16 {
17     ++cnt;
18     e[cnt].w = w;
19     e[cnt].to = v;
20     e[cnt].nxt = head[u];
21     head[u] = cnt;
22 }
23 
24 void spfa(int a)
25 {
26     memset(dis,0x3f,sizeof(dis));
27     memset(vis,0,sizeof(vis));
28     while (!q.empty()) q.pop();
29     q.push(1);
30     vis[1] = true;
31     dis[1] = 0;
32     pre[a][1] = 0;
33     while (!q.empty())
34     {
35         int u = q.front();
36         q.pop();
37         for (int i=head[u]; i; i=e[i].nxt)
38         {
39             int w = e[i].w;
40             int v = e[i].to;
41             if (pd[a][v]) continue;
42             if (dis[v]>dis[u]+w)
43             {
44                 pre[a][v] = u;
45                 dis[v] = dis[u]+w;
46                 if(!vis[v])
47                 {
48                     q.push(v);
49                     vis[v] = true;
50                 }
51             }
52         }
53         vis[u] = false;
54     }
55     int p = m,pp = m,flag = 1;
56     if (a>=2) while (p!=0 && pp!=0)
57     {
58         if (p!=pp)
59         {
60             flag = 0;
61             break;
62         }
63         p = pre[a][p];
64         pp = pre[a-1][pp];
65     }
66     if (flag==0) ans += k;
67     ans += dis[m];
68 }
69 
70 int main()
71 {
72     scanf("%d%d%d%d",&n,&m,&k,&t);
73     for (int x,y,z,i=1; i<=t; ++i)
74     {
75         scanf("%d%d%d",&x,&y,&z);
76         add(x,y,z);
77         add(y,x,z);
78     }
79     scanf("%d",&d);
80     for (int x,y,z,i=1; i<=d; ++i)
81     {
82         scanf("%d%d%d",&x,&y,&z);
83         for (int j=y; j<=z; ++j)
84             pd[j][x] = true;
85     }
86     for (int i=1; i<=n; ++i)
87         spfa(i);
88     printf("%d",ans);
89     return 0;
90 }

View Code

AC代码

 1 #include<cstdio>
 2 #include<queue>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 const int MAXN = 25;
 7 const int MAXT = 110; 
 8 const int INF = 1e8;
 9 struct Edge{
10     int to,w,nxt;    
11 }e[1010];
12 int dis[MAXN],head[MAXN];
13 bool pd[MAXN][MAXT],vis[MAXN];
14 int cost[MAXT][MAXT],f[MAXT];
15 int d,n,m,k,t,ans,cnt;
16 queue<int>q;
17 
18 void add(int u,int v,int w)
19 {
20     ++cnt;
21     e[cnt].w = w;
22     e[cnt].to = v;
23     e[cnt].nxt = head[u];
24     head[u] = cnt;
25 }
26 bool juge(int v,int a,int b)
27 {
28     for (int i=a; i<=b; ++i)
29         if (pd[v][i]) return false;
30     return true;
31 }
32 int spfa(int a,int b)
33 {
34     if (!juge(1,a,b)) return INF;
35     memset(vis,0,sizeof(vis));
36     while (!q.empty()) q.pop();
37     for (int i=1; i<=m; ++i) dis[i] = INF;
38     q.push(1);
39     vis[1] = true;
40     dis[1] = 0;
41     while (!q.empty())
42     {
43         int u = q.front();
44         q.pop();
45         for (int i=head[u]; i; i=e[i].nxt)
46         {
47             int w = e[i].w;
48             int v = e[i].to;
49             if (!juge(v,a,b)) continue;
50             if (dis[v]>dis[u]+w)
51             {
52                 dis[v] = dis[u]+w;
53                 if(!vis[v])
54                 {
55                     q.push(v);
56                     vis[v] = true;
57                 }
58             }
59         }
60         vis[u] = false;
61     }
62     if(dis[m]==INF) return INF;
63     else return dis[m]*(b-a+1);
64 }
65 
66 int main()
67 {
68     scanf("%d%d%d%d",&n,&m,&k,&t);
69     for (int x,y,z,i=1; i<=t; ++i)
70     {
71         scanf("%d%d%d",&x,&y,&z);
72         add(x,y,z);
73         add(y,x,z);
74     }
75     scanf("%d",&d);
76     for (int x,y,z,i=1; i<=d; ++i)
77     {
78         scanf("%d%d%d",&x,&y,&z);
79         for (int j=y; j<=z; ++j)
80             pd[x][j] = true;
81     }
82     
83     for (int i=1; i<=n; ++i)
84         for (int j=i; j<=n; ++j)
85             cost[i][j] = spfa(i,j);
86     f[0] = 0;
87     for (int i=1; i<=n; i++)
88         f[i] = cost[1][i];
89     for (int i=2; i<=n; ++i)
90         for (int j=i-1; j>=1; --j)
91             if (cost[j+1][i]!=INF)     f[i] = min(f[i],f[j]+cost[j+1][i]+k);
92             else break;
93     printf("%d",f[n]);
94     return 0;
95 }

View Code