nyoj973 天下第一 (spfa算法)

nyoj973 天下第一 (spfa算法)

题目973​​题目信息​​​​运行结果​​​​本题排行​​​​讨论区​​

天下第一

1000 ms  |  内存限制： 65535

3

AC_Grazy一直对江湖羡慕不已,向往着大碗吃肉大碗喝酒的豪情，但是“人在江湖漂,怎能

不挨刀",”人在江湖身不由己",如果自己的武功太差,在江湖会死的很惨，但是AC_Grazy没有

武功秘籍练不了绝世武功.有道是“山重水复疑无路,柳暗花明又一村”,在AC_Grazy家里面

竟然藏着一本书,书名竟然叫做【超级外挂】,竟然能在各种武功之间进行转化,据说是他爷

爷的爷爷的...爷爷传下来的...

闲着无事便拿来看看,只看一眼便再也停不下了,只见上面写着“纵横武林打遍天下无敌手武功心法秘籍收录”.

翻开第一篇一看竟然是【降龙十八掌】...

心法只是一个修练武功的途径,重要的是真气的多少,于是他便想利用外挂让武功之间进行转

化，来让真气无限增加，但是这个心法只能按照顺序转化，我们分别用 1号和2号来代替两种功法 当然转化会有一定的转化率f

比如1 0.5 2 便是把 1的一半真气转化给2 ,为了简化问题，我们每次都从1号秘籍开始进行转化,如果其中一个秘籍转化断了，那么以后的功法就不能转换。

输入：首先输入一个数 T(T<=20)表示T组数据

然后输入两个数n(2<=n<=500)和m(1=

示有n种秘籍，随后的m行分别输入

秘籍u(n>=u>0) 转化率 f (0

输出 输出：如果可以无限增加真气输出Yes否则输出No. 样例输入

2 3 3 1 2 2 2 2 3 3 2 1 4 3 1 2 2 3 2 4 4 2 3

样例输出

Yes No

上传者 ​​ACM_王亚龙​​

超时了两次

也发现自己的毛病 看到了图论题就想深搜 却不知 深搜那么耗时 容易超时

这是我第一次用深搜做的 肯定超时了。。

#include #include #include #include using namespace std;double map[505][505];int n,m,t;bool flag,vis[505][505];vectorlist[505];void dfs(int pos,double sum){ if(pos==1) ++t; if(t>=2) { if(sum>=1) flag=true; return ; } for(int i=0;i

AC代码 spfa算法

#include #include #include #include #include using namespace std;double f[505][505],dist[505];//f为转换率 dist源点到各点的路径 int n,m,sum[505];//n为点的个数,m为边的个数,sum为进队列的次数 bool in[505];//判断是否在队列中 vectorlist[505];//邻接表 queues;bool spfa(int pos){ while(!s.empty()) s.pop(); sum[pos]++; in[pos]=true; dist[pos]=1.0; s.push(pos); while(!s.empty()) { pos=s.front(); s.pop(); in[pos]=false; for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。