天下第一
时间限制：1000 ms | 内存限制：65535 KB
难度：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=<m<=2000)分别表
示有n种秘籍，随后的m行分别输入
秘籍u(n>=u>0) 转化率 f (0<f<=10)秘籍 v.(0<v<=n) - 输出
- 输出：如果可以无限增加真气输出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- 上传者
#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int v,next;
double w;
}edge[2020];
int head[2020];
double dis[2020];
bool vis[1010];
int used[1010];
int m,n,cnt;
bool SPFA(int sx)
{
queue<int>q;
memset(vis,false,sizeof(vis));
memset(dis,0,sizeof(dis));
memset(used,0,sizeof(used));
q.push(sx);
vis[sx]=true;
used[sx]++;
dis[sx]=1.0;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=false;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
double f=edge[i].w;
if(dis[u]*f>dis[v])
{
dis[v]=dis[u]*f;
if(!vis[v])
{
vis[v]=1;
q.push(v);
used[v]++;
if(used[v]>=n)
return true;
}
}
}
}
return false;
}
int main()
{
int t;
cin>>t;
while(t--)
{
memset(head,-1,sizeof(head));
cnt=0;
cin>>n>>m;
int x,y;
double w;
for(int i=0;i<m;i++)
{
cin>>x>>w>>y;
edge[cnt].v=y;
edge[cnt].w=w;
edge[cnt].next=head[x];
head[x]=cnt++;
}
if(SPFA(1))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}