BZOJ1003 物流运输 题解
2024-10-09 05:05:31
发现\(n,m\)很小,我们可以先把任意\(2\)天的最短路都给求出来,考虑\(DP\),设\(f[i][j]\)表示\(j+1\)~ \(i\)这几天内走的是最短路线的最优方案,显然最优情况下\(j+1\)~ \(i\)天走的是同一条路。
#include <bits/stdc++.h>
#define int long long
int n,m,k,E,N;
int head[1000000],tot;
int r[111];
int cn[111][111];
int dis[1000000];
int min[111][111];
std::queue<int>q;
struct edge{
int to,nxt,w;
}e[1000000];
void add(int x,int y,int z){
e[++tot]={y,head[x],z};
head[x]=tot;
}
void D(int d1,int d2){
for(int i=1;i<=m;++i)dis[i]=1e14;
dis[1]=0;
q.push(1);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x],y,f;i;i=e[i].nxt){
y=e[i].to;f=0;
for(int j=d1;j<=d2;++j)f|=cn[y][j];
if(f)continue;
if(dis[y]>dis[x]+e[i].w){
dis[y]=dis[x]+e[i].w;
q.push(y);
}
}
}
min[d1][d2]=dis[m];
}
main(){
scanf("%lld%lld%lld%lld",&n,&m,&k,&E);
for(int i=1,x,y,z;i<=E;++i){
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
scanf("%lld",&N);
for(int i=1,x,y,z;i<=N;++i){
scanf("%lld%lld%lld",&x,&y,&z);
for(int j=y;j<=z;++j)
cn[x][j]=1;
}
for(int i=0;i<=n;++i)
for(int j=i;j<=n;++j)
D(i,j);
r[0]=0LL;
for(int i=1;i<=n;++i)r[i]=1e14;
for(int i=1;i<=n;++i)
for(int j=0;j<i;++j)
r[i]=std::min(r[i],r[j]+k*(j>0)+min[j+1][i]*(i-j));
printf("%lld\n",r[n]);
return 0;
}
最新文章
- Atitit.你这些项目不都是模板吗?不是原创&#160;&#160;集成和整合的方式大总结
- iOS开发常用快捷键
- 使用JMeter进行简单的压力测试
- Css Js Loader For Zencart
- 采用sqlserver的缺省配置,在生产环境经常碰到系统响应慢(甚至hung的情况)
- jax-rs中的一些参数标注简介(@PathParam,@QueryParam,@MatrixParam,@HeaderParam,@FormParam,@CookieParam)
- JS 中面向对象的5种写法
- android studio 中怎么使用adb无线调试
- 浅谈AndroidManifest.xml与R.java及各个目录的作用
- Qt中的 Size Hints 和 Size Policies
- xcode 预编译头文件
- *MySQL卸载之后无法重装,卡在Apply security settings:Error Nr.1045
- OpenDigg安卓开源项目月报201704
- spring整合axis2(最小配置化)的示例
- Thinkphp环境搭建
- ArcGIS——2015年中国各省GDP总量分级图(6等级)
- 2019/2/23Scala学习开始(Scala简介)
- Data Consistency Primer
- 牛客练习赛7 E 珂朵莉的数列
- visio2003 数据表模型中显示字段类型和注释