一直在第44个测试点上WA掉.......
查看原帖
一直在第44个测试点上WA掉.......
546086
Francais_Drake楼主2021/12/16 21:56
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
map<string,int> Mp;
struct edge{int to,nxt;double ed;}e[10000];
string s;
int h[35],cnt[35];
bool in[35];
int n,m,x,y,num,tot;
double ed,dis[35];
queue<int> q;
int main(){
	dis[0]=1;
	while(1){
		scanf("%d",&n);
		if(!n) return 0;
		memset(h,0,sizeof(h));
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<35;++i) dis[i]=0;
		Mp.clear();++num;tot=n;
		for(int i=1;i<=n;++i){
			cin>>s;Mp[s]=i;
			e[i]=(edge){i,h[0],1};h[0]=i;
		}
		scanf("%d",&m);
		while(m--){
			cin>>s;x=Mp[s];
			scanf("%lf",&ed);
			cin>>s;y=Mp[s];
			e[++tot]=(edge){y,h[x],ed};h[x]=tot;
		}
		q.push(0);
		while(!q.empty()){
			x=q.front();
			q.pop();in[x]=0;
			for(int i=h[x];i;i=e[i].nxt){
				y=e[i].to;ed=e[i].ed;
				if(dis[x]*ed>dis[y]){
					dis[y]=dis[x]*ed;
					cnt[y]=cnt[x]+1;
					if(cnt[y]>n) goto suc;
					if(!in[y]){in[y]=1;q.push(y);}
				}
			}
		}
		printf("Case %d: No\n",num);continue;
		suc:printf("Case %d: Yes\n",num);
			while(!q.empty()) q.pop();
	}
}
2021/12/16 21:56
加载中...