• 欢迎光临~

[AHOI2014/JSOI2014]骑士游戏

开发技术 开发技术 2022-12-14 次浏览
链接:https://www.luogu.com.cn/problem/P4042 题目描述:对于一个怪物$i$,可以花费$c_{i}$的代价将其变为一个怪物集合,或花费$c2_{i}$的代价消灭他。求消灭怪物$1$的最小代价。 题解:由于这里涉及到了变化的传递,我们可以将原问题抽象为一个图,每一个点它可以花费$c2_{i}$的代价到达一个死亡节点或花费$c_{i}$的代价到达一个点集。 由于这个点集无法被直接表示,那么我们可以将他化为求点集的最小消灭代价之和$+$$c_{i}$,直接消灭也就是可以将$i$的最小消灭代价化为$c2_{i}$。 我们可以将$dijkstra$稍微改改,将所有点的$dis$初始化为$c2_{i}$,每一次将转移变为求集的最小消灭代价之和$+$$c_{i}$,也像$dijkstra$那样跑就行了。 ``` #include #include #include using namespace std; struct node { long long v,nxt,data; bool vis; }; node edge[2000001]; struct reads { long long num,data; bool operator < (const reads &a)const { return data>a.data; } }; long long dis[200001],dis2[200001]; int len,head[200001],n,in[200001],cnt[200001]; bool used[200001]; priority_queueq; reads tmp; reads make_reads(int x,long long y) { tmp.num=x; tmp.data=y; return tmp; } void add(int x,int y,long long z) { edge[++len].v=y; edge[len].data=z; edge[len].nxt=head[x]; head[x]=len; return; } void dijkstra() { int top; while (!q.empty()) { top=q.top().num; q.pop(); if (used[top]) continue; used[top]=1; for (int i=head[top];i>0;i=edge[i].nxt) { if (!edge[i].vis&&cnt[edge[i].v]==in[edge[i].v]-1&&dis[edge[i].v]>dis2[edge[i].v]+dis[top]+edge[i].data) { edge[i].vis=1; cnt[edge[i].v]++; dis[edge[i].v]=dis2[edge[i].v]+dis[top]+edge[i].data; q.push(make_reads(edge[i].v,dis[edge[i].v])); } if (!edge[i].vis&&cnt[edge[i].v]>w; add(w,i,x); in[i]++; } dis[i]=y; } for (int i=1;i<=n;++i) q.push(make_reads(i,dis[i])); dijkstra(); printf("%lldn",dis[1]); return 0; }
程序员灯塔
转载请注明原文链接:[AHOI2014/JSOI2014]骑士游戏
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com