AtCoder Beginner Contest 164 E(二维 图上dp)
发布日期:2021-06-29 12:57:57
浏览次数:3
分类:技术文章
本文共 1869 字,大约阅读时间需要 6 分钟。
E - Two Currencies
题意:给你n节点m条边的无向图
每条边有s 和 t ,s 代表 经过这条路要花费s银币,t代表走这条路需要消耗的时间
每个节点有c[i]、d[i] 代表在i这个节点兑换c个银币消耗d时间。
问从1节点出发 到达其他节点时的最小时间
初始金币为s
做法:设dp[i][j] 代表 到达i这个节点拥有j银币时的最小时间。
进行n+1轮的图上dp即可。
注意要先枚举被到达的节点i 再枚举从起始点v->i 的dp转移。
如果是枚举i ->v 会wa在倒数第二个点。原因不详。。
要从v的父亲转移过来,不能从v往外辐射,不知道是不是我代码问题 会wa在倒数第二个点
#include#define rep(i,a,b) for(int i=a;i<=(b);++i)#define per(i,a,b) for(int i=a;i>=(b);--i)#define mem(a,x) memset(a,x,sizeof(a))#define pb push_back#define pi pair #define mk make_pairusing namespace std;typedef long long ll;ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}const ll inf=0x3f3f3f3f;const int N=100;struct edge{ int v; ll s,t; int ne;}e[N<<1];int n,m,cnt,head[N];ll s,dis[N],c[N],d[N],dp[N][3000];void add(int u,int v,ll w,ll t){ e[++cnt]={v,w,t,head[u]}; head[u]=cnt; e[++cnt]={u,w,t,head[v]}; head[v]=cnt;}void bfs(){ if(s>=2500) s=2500; dp[1][s]=0; for(int up=1;up<=n+2;++up){ for(int i=1;i<=n;++i){ for(int j=head[i];j;j=e[j].ne){ for(int now=0;now<=2500;++now){ if(now+e[j].s>=0){ dp[i][now]=min(dp[i][now],dp[e[j].v][now+e[j].s]+e[j].t); //dp[e[j].v][now-e[j].s]=min(dp[e[j].v][now-e[j].s],dp[i][now]+e[j].t); //这样wa } } } for(int now=0;now<=2500;now++){ if(now-c[i]>=0){ dp[i][now]=min(dp[i][now-c[i]]+d[i],dp[i][now]); } } } }}void solve(){ cin>>n>>m>>s; mem(dp,inf); rep(i,1,m) { int u,v;ll a,b; cin>>u>>v>>a>>b; add(u,v,a,b); } rep(i,1,n) cin>>c[i]>>d[i]; bfs(); for(int i=2;i<=n;++i){ ll ans=1e18; for(int now=0;now<=2500;++now) ans=min(ans,dp[i][now]); printf("%lld\n",ans); }}int main(){ solve();}
转载地址:https://ccsudeer.blog.csdn.net/article/details/105794508 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月28日 06时10分42秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Java LinkedHashMap
2019-04-29
JPA 多线程同时对一条数据进行Update的问题
2019-04-29
JPA 多线程对数据进行更新,Update和Insert同时存在的问题
2019-04-29
Java 高性能队列Disruptor
2019-04-29
SpringBoot 使用https
2019-04-29
Java 读写锁
2019-04-29
JVM Minor GC、Full GC和Major GC
2019-04-29
SpringBoot @Scheduled 执行两次的问题
2019-04-29
tomcat配置JVM
2019-04-29
Ubuntu软件安装&卸载
2019-04-29
面试笔试易错知识点Java篇八
2019-04-29
弹性事务框架ETF4J——面向Java微服务的交易最终一致性解决方案
2019-04-29
【Scala 教程】Scala 条件与循环语句
2019-04-29
【Scala 教程】Scala 集合类型
2019-04-29
JAVA 线程同步机制 synchronized
2019-04-29
MySQL 安装教程(无脑版)
2019-04-29
IDEA 怎么删除一个Module
2019-04-29
走进数据科学:最好是通过比网课更好的方法
2019-04-29
AI革命第一步:最容易被忽略但必不可少的物联网
2019-04-29