悬棺
查看原帖
悬棺
636409
Headofstate1945楼主2025/1/9 12:00
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,cnt=0;
vector<pair<int,double>>mp[N];
double dis[N];
bool vis[N];
int cat[N];
bool spfa(int s){
	queue<int>q;
	q.push(s);
	dis[s]=1.0;
	vis[s]=1;
	while(q.size()){
		int u=q.front();q.pop();
		vis[u]=0;
		for(auto [v,w]:mp[u]){
			if(dis[v]<dis[u]*w){
				dis[v]=dis[u]*w;
				cat[v]=cat[u]+1;
				if(cat[v]>=n)return 1;
				if(!vis[v])vis[v]=1,q.push(v);
			}	
		}
	}
	return 0;
	
}
void solve(){
	map<string,int>cure;	
	memset(cat,0,sizeof cat);
	for(int i=1;i<=n;i++)mp[i].clear();
	for(int i=1;i<=n;i++)dis[i]=0;
	cnt++;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		cure[s]=i;
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		string x,y;
		double z;
		cin>>x>>z>>y;
		mp[cure[x]].push_back({cure[y],z});
	}
	for(int i=1;i<=n;i++){
		if(!cat[i]&&spfa(i)){
			printf("Case %d: Yes\n",cnt);
			return;
		}
	}
	printf("Case %d: No\n",cnt);	
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);

	while(cin>>n,n){	
		
		solve();
	}
	return 0;
}
2025/1/9 12:00
加载中...