这个 dp 其实不是那么难, 状态其实很好想, 但是细节有少许偏差.
当时我并没有想到最短路要在 dp 之外写, 后来看题解之后发现要预处理出来每段时间 1~M 的最短路, 然后直接 dp.
题目:
Description
物流公司要把一批货物从码头 A 运到码头 B. 由于货物量比较大, 需要 n 天才能运完. 货物运输过程中一般要转
停好几个码头. 物流公司通常会设计一条固定的运输路线, 以便对整个运输过程实施严格的管理和跟踪. 由于各种
因素的存在, 有的时候某个码头会无法装卸货物. 这时候就必须修改运输路线, 让货物能够按时到达目的地. 但是
修改路线是一件十分麻烦的事情, 会带来额外的成本. 因此物流公司希望能够订一个 n 天的运输计划, 使得总成本
尽可能地小.
Input
第一行是四个整数 n(1<=n<=100),m(1<=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 的运输路线.
Output
包括了一个整数表示最小的总成本. 总成本 = n 天运输路线长度之和 + K * 改变运输路线的次数.
- Sample Input
- 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
代码:
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<queue>
- using namespace std;
- #define duke(i,a,n) for(int i = a;i <= n;i++)
- #define lv(i,a,n) for(int i = a;i>= n;i--)
- #define clear(a) memset(a,0,sizeof(a))
- const int INF = 1 <<30;
- template <class T>
- void read(T &x)
- {
- char c;
- int op = 0;
- while(c = getchar(),c> '9' || c <'0')
- if(c == '-') op = 1;
- x = c - '0';
- while(c = getchar(),c>= '0' && c <= '9')
- x = x * 10 + c - '0';
- if(op == 1)
- x = -x;
- }
- int lst[10005],len = 0;
- struct node
- {
- int l,r,w,nxt;
- }a[10005];
- int mp[200][200];
- void add(int x,int y,int w)
- {
- a[++len].l = x;
- a[len].r = y;
- a[len].w = w;
- a[len].nxt = lst[x];
- lst[x] = len;
- }
- int d[10002];
- long long dp[10002];
- int vis[10003],dis[200][205];
- int n,m,k,e;
- int spfa(int s,int b,int e)
- {
- memset(d,0x3f,sizeof(d));
- clear(vis);
- queue <int> q;
- q.push(s);
- d[s] = 0;
- while(!q.empty())
- {
- int x = q.front();
- vis[x] = 0;
- q.pop();
- for(int k = lst[x];k;k = a[k].nxt)
- {
- int y = a[k].r;
- if(mp[y][e] - mp[y][b - 1]> 0)
- continue;
- if(d[y]> d[x] + a[k].w)
- {
- d[y] = d[x] + a[k].w;
- if(!vis[y])
- {
- q.push(y);
- vis[y] = 1;
- }
- }
- }
- }
- dis[b][e] = d[m];
- }
- int x,y,z;
- int main()
- {
- clear(mp);
- read(n);read(m);read(k);read(e);
- duke(i,1,e)
- {
- read(x);read(y);read(z);
- add(x,y,z);
- add(y,x,z);
- }
- int d;
- read(d);
- duke(i,1,d)
- {
- read(x);read(y);read(z);
- duke(j,y,z)
- {
- mp[x][j] = 1;
- }
- }
- duke(i,1,m)
- {
- duke(j,1,n)
- {
- mp[i][j] += mp[i][j - 1];
- }
- }
- duke(i,1,n)
- {
- duke(j,i,n)
- {
- spfa(1,i,j);
- }
- }
- dp[0] = -k;
- duke(i,1,n)
- {
- dp[i] = 0x3f3f3f3f;
- for(int j = 0;j < i;j++)
- {
- dp[i] = min(dp[i],dp[j] + 1ll * dis[j + 1][i] * (i - j) + k);
- }
- }
- printf("%lld\n",dp[n]);
- return 0;
- }
- /*
- 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
- */
来源: http://www.bubuko.com/infodetail-2729536.html