d[i]代表从起点出发可以获得最多的钱数，松弛是d[v]=r*d[u]，求最长路，看有没有正环
然后这题输入有毒，千万别用cin 因为是大输入，组数比较多，然后找字符串用strcmp就好，千万不要用map
这题刚开始我T了（用的map），还以为组数很多卡spfa呢，然后我上网看了看都是floyd的，然后我用floyd写了一发，891ms过了
然后我感觉spfa的复杂度也不是很大，就是看有没有正环，所以我觉得可能是map+cin的锅，然后改了一发，用的spfa，47ms过
真是，算了，实质是本蒟蒻经验不足（其实也不是没做过卡输入的）
这是map+cin+floyd
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<iostream>
#include<string>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
const int N=;
const int INF=0x3f3f3f3f;
map<string,int>mp;
double d[N][N];
int n,m;
bool fun(){
for(int k=;k<=n;++k)
for(int i=;i<=n;++i)
for(int j=;j<=n;++j)
d[i][j]=max(d[i][j],d[i][k]*d[k][j]);
for(int i=;i<=n;++i)
if(d[i][i]>)return true;
return false;
}
int main(){
int cas=;
while(~scanf("%d",&n),n){
mp.clear();
for(int i=;i<=n;++i){
string t;
cin>>t;
mp[t]=i;
}
memset(d,,sizeof(d));
for(int i=;i<=n;++i)
d[i][i]=;
scanf("%d",&m);
while(m--){
string x,y;
double r;
cin>>x>>r>>y;
d[mp[x]][mp[y]]=r;
}
printf("Case %d: ",++cas);
if(fun())printf("Yes\n");
else printf("No\n");
}
}
这是strcmp+spfa（推荐看这个）
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<iostream>
#include<string>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
const int N=;
const int INF=0x3f3f3f3f;
struct Edge{
int v,next;
double r;
}edge[N*N];
int n,m,head[N],tot,cnt[N];
void add(int u,int v,double r){
edge[tot].v=v;
edge[tot].r=r;
edge[tot].next=head[u];
head[u]=tot++;
}
bool inq[N];
double d[N];
queue<int>q;
bool spfa(int s){
for(int i=;i<=n;++i)
d[i]=cnt[i]=inq[i]=;
d[s]=,++cnt[s],inq[s]=true;
while(!q.empty())q.pop();
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
inq[u]=false;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].v;
if(d[u]*edge[i].r>d[v]){
d[v]=d[u]*edge[i].r;
if(!inq[v]){
inq[v]=true;
if(++cnt[v]>n)return true;
q.push(v);
}
} }
if(d[s]>)return true;
}
return false;
}
char a[N][];
int find(char *s){
for(int i=;i<=n;++i)
if(!strcmp(s,a[i]))return i;
}
int main(){
int cas=;
while(~scanf("%d",&n),n){
memset(head,-,sizeof(head)),tot=;
for(int i=;i<=n;++i)
scanf("%s",a[i]);
scanf("%d",&m);
while(m--){
char s[];
double r;
scanf("%s%lf",s,&r);
int u=find(s);
scanf("%s",s);
int v=find(s);
add(u,v,r);
}
printf("Case %d: ",++cas);
if(spfa())printf("Yes\n");
else printf("No\n");
}
}