「JoyOI1136」火焰巨魔的惆怅
背景 Background
JoyOI2月月赛第一道
巨魔家族在某天受到了其他种族的屠杀，作为一个英雄，他主动担任了断后的任务，但是，在巨魔家族整体转移过后，火焰巨魔却被困住了，他出逃的方式也只有召唤小火人这一种方式，所以请你帮助他。
巨魔家族在某天受到了其他种族的屠杀，作为一个英雄，他主动担任了断后的任务，但是，在巨魔家族整体转移过后，火焰巨魔却被困住了，他出逃的方式也只有召唤小火人这一种方式，所以请你帮助他。
描述 Description
我们把火焰巨魔所处的位置抽象成一张有向图，他的位置就是1号点位，目的就是走到第N号点位，因为小火人会裂嘛，所以我们可以看做每走一条路，小火人的数量都会加倍，而每条路上的敌人有多强，会消耗多少小火人c[i]也会给出(c[i]为负值)；当然有些时候路上也会遇到魔法泉之类的东西，这时候就可以补充一些小火人咯(c[i]为正值）。如果小火人死光了，那么火焰巨魔也就可以看做是挂了，毕竟智力型英雄就是脆啊。希望你帮助火焰巨魔用最少的初始小火人逃离这次屠杀。
输入格式 InputFormat
第一行两个数N（<=50000），M（<=100000）表示点位数与边数。
一下M行，每行三个数a，b，c表示a，b两点间的边权是c（|c|<=10000）
一下M行，每行三个数a，b，c表示a，b两点间的边权是c（|c|<=10000）
输出格式 OutputFormat
输出仅一个整数，表示最小初始小火人数。
输入格式 InputFormat
5 4
1 2 -3
1 3 -6
3 4 1
4 5 -9
样例输出 SampleOutput
4
数据范围和注释 Hint
初始小火人为4个，到3点剩2个，到4变成5个，到5剩1个。
所以初始最少为4，更少的小火人是不足以走到5号点位的。
所以初始最少为4，更少的小火人是不足以走到5号点位的。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m,cnt; struct data{ int to,next,v; }e[100001]; int head[50001],q[50001],dis[50001]; bool inq[50001]; int get(int x){if(x%2!=0)x++;x/=2;return x;} void insert(int u,int v,int w) { cnt++; e[cnt].to=u; e[cnt].v=-w; e[cnt].next=head[v]; head[v]=cnt; } void spfa() { memset(dis,127/3,sizeof(dis)); int t=0,w=1,i,now; dis[n]=1;q[0]=n;inq[n]=1; while(t!=w) { now=q[t];t++;if(t==n)t=1; i=head[now]; while(i) { if(get(dis[now]+e[i].v)<dis[e[i].to]) { dis[e[i].to]=get(dis[now]+e[i].v); if(dis[e[i].to]<1)dis[e[i].to]=1; if(!inq[e[i].to]) { inq[e[i].to]=1; q[w++]=e[i].to; if(w==n)w=1; } } i=e[i].next; } inq[now]=0; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); insert(u,v,w); } spfa(); printf("%d",dis[1]); return 0; } |
Subscribe
计数器 9794929
OI 课件=>
OI 课件=>