标签：JSOI2014 int AHOI2014 long edge 骑士 data top dis
链接：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]<in[edge[i].v]-1) {="" edge[i].vis="1;" cnt[edge[i].v]++;="" dis2[edge[i].v]="dis2[edge[i].v]+dis[top];" }="" return;="" int="" main()="" long="" x,y,z,w;="" scanf("%lld",&n);="" for="" (int="" i="1;i<=n;++i)" scanf("%lld%lld%lld",&x,&y,&z);="" while="" (z--)="" cin="">>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("%lld\n",dis[1]);
return 0;
}
标签：JSOI2014,
int,
AHOI2014,
long,
edge,
骑士,
data,
top,
dis
From： https://www.cnblogs.com/zhouhuanyi/p/16983514.html