emmmmm又是SPFA没啥好讲的板子题
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <
string>
#include <map>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <
set>
#include <vector>
//const int maxn = 1e5+5;
#define ll long long
ll gcd(ll a,ll b){return b?gcd(b,a%
b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*
b;}
//const int inf = 0x6fffffff;
#define MAX INT_MAX
#define FOR(i,a,b) for( int i = a;i <= b;++i)
#define bug cout<<"--------------"<<endl
using namespace std;
string s[
35];
int ver[
1100],next[
1100],head[
1100],ans[
1100],vis[
1100];
double edge[
1100],d[
1100];
int tot,n;
void add(
int x,
int y,
double z)
{
ver[++tot] = y,edge[tot] = z,next[tot] = head[x] , head[x] =
tot;
}
int spfa(
int first)
{
memset(vis,0,
sizeof(vis));
memset(d,0,
sizeof(d));
memset(ans,0,
sizeof(ans));
d[first] =
10;
vis[first] =
1;
ans[first] ++
;
queue<
int>
que;
que.push(first);
while(que.size())
{
int x =
que.front();que.pop();
vis[x] =
0;
// cout<<x<<" ";
// FOR(i,1,3)
// cout<<vis[i]<<" ";
// cout<<endl;
for(
int i=head[x];i;i=
next[i])
{
int y =
ver[i];
double z =
edge[i];
// cout<<y<<" "<<d[y]<<" "<<d[x]*z<<endl;
if(d[y] <(
double) d[x] *
z)
{
d[y] =(
double) d[x] *
z;
if(vis[y] ==
1)
continue;
vis[y] =
1;
que.push(y);
ans[y]++
;
if(ans[y] >=
n)
{
return 1;
}
}
}
}
return 0;
}
void clearr()
{
tot =
0;
memset(head,0,
sizeof(head));
memset(next,0,
sizeof(next));
memset(ver,0,
sizeof(ver));
memset(edge,0,
sizeof(edge));
}
int main()
{
// freopen("C:\\Users\\方瑞\\Desktop\\input.txt","r",stdin);
// freopen("C:\\Users\\方瑞\\Desktop\\output.txt","w",stdout);
ios::sync_with_stdio(
false);
int casee=
0;
while((cin>>n) &&
n)
{
clearr();
FOR(i,1,n) cin>>
s[i];
int m;
cin>>
m;
while(m--
)
{
string s1,s2;
double hhh;
cin>>s1>>hhh>>
s2;
int fx,fy;
for(
int i=
1;i<=n;++
i)
{
if(s[i] == s1) fx =
i;
if(s[i] == s2) fy =
i;
}
// cout<<fx<<" "<<fy<<" "<<hhh<<endl;
add(fx,fy,hhh);
}
int flag =
0;
for(
int i=
1;i<=n;++
i)
{
if(spfa(i) ==
1)
{
flag =
1;
break;
}
}
if(flag ==
1) cout<<
"Case "<<++casee<<
": Yes"<<
endl;
else cout<<
"Case "<<++casee<<
": No"<<
endl;
}
}
转载于:https://www.cnblogs.com/jrfr/p/11370942.html
