首页 > 代码库 > Tyvj 1176 火焰巨魔的惆怅
Tyvj 1176 火焰巨魔的惆怅
Tyvj 1176 火焰巨魔的惆怅
背景
TYVJ2月月赛第一道
巨魔家族在某天受到了其他种族的屠杀，作为一个英雄，他主动担任了断后的任务，但是，在巨魔家族整体转移过后，火焰巨魔却被困住了，他出逃的方式也只有召唤小火人这一种方式，所以请你帮助他。
巨魔家族在某天受到了其他种族的屠杀，作为一个英雄，他主动担任了断后的任务，但是，在巨魔家族整体转移过后，火焰巨魔却被困住了，他出逃的方式也只有召唤小火人这一种方式，所以请你帮助他。
描述
我们把火焰巨魔所处的位置抽象成一张有向图，他的位置就是1号点位，目的就是走到第N号点位，因为小火人会裂嘛，所以我们可以看做每走一条路，小火人的数量都会加倍，而每条路上的敌人有多强，会消耗多少小火人c[i]也会给出(c[i]为负值)；当然有些时候路上也会遇到魔法泉之类的东西，这时候就可以补充一些小火人咯(c[i]为正值）。如果小火人死光了，那么火焰巨魔也就可以看做是挂了，毕竟智力型英雄就是脆啊。希望你帮助火焰巨魔用最少的初始小火人逃离这次屠杀。
输入格式
第一行两个数N（<=50000），M（<=100000）表示点位数与边数。
一下M行，每行三个数a，b，c表示a，b两点间的边权是c（|c|<=10000）
一下M行，每行三个数a，b，c表示a，b两点间的边权是c（|c|<=10000）
输出格式
输出仅一个整数，表示最小初始小火人数。
测试样例1
输入
5 4
1 2 -3
1 3 -6
3 4 1
4 5 -9
输出
4
备注
初始小火人为4个，到3点剩2个，到4变成5个，到5剩1个。
所以初始最少为4，更少的小火人是不足以走到5号点位的。from wsd TYVJ月赛出题组
所以初始最少为4，更少的小火人是不足以走到5号点位的。from wsd TYVJ月赛出题组
思路：
1、由于要求的是从起点到达终点最少出发的小火人，所以是一个路径寻找问题，所以要用到最短路
2、由于小火人最少是1，所以到终点后小火人数量一定是1，否则就必须要在起点派出更多小火人
3、在最短路中，目的是求长度最小，放入队列的必要条件是可以把该点长度变小，所以此题中放入的条件是可以把所需要的火人数量变小
4、从终点开始，做spfa，则由用来松弛的点走到当前节点的最小火人数设为x，则2x + g[now][i] = d[now]，可知x可能不为正整数，若为浮点数则向上取整，若x≤0，则将x设为1，然后去比较d[i]进行松弛，最后d[1]便是正确答案
#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<queue>using namespace std;const int maxn = 100005;const int maxint = ~0U>>1;struct edge{ int v; int w;};int n,m,vis[maxn],d[maxn];vector<edge> g[maxn];void input(){ cin>>n>>m; int u,v,w; edge tmp; for(int i = 1;i <= m;i++){ scanf("%d%d%d",&u,&v,&w); tmp.v = u; tmp.w = w; g[v].push_back(tmp); } for(int i = 1;i <= n;i++){ vis[i] = 0; d[i] = maxint; }}void spfa(){ queue<int> q; q.push(n); d[n] = 1; vis[n] = 1; int now,to,add; while(!q.empty()){ now = q.front(); q.pop(); vis[now] = 0; for(int i = 0;i < g[now].size();i++){ to = g[now][i].v; add = (d[now] - g[now][i].w) >> 1; if((d[now]-g[now][i].w) & 1) add++; if(add <= 0) add = 1; if(d[to] > add){ d[to] = add; if(!vis[to]){ vis[to] = 1; q.push(to); } } } }} int main(){ input(); spfa(); cout<<d[1]; return 0;}
Tyvj 1176 火焰巨魔的惆怅
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。