spfa跑个乘积最长路 如果dis[1] > 1 说明能套利

#include<bits/stdc++.h>
using namespace std;
const int N = 35;
unordered_map<string, int> ump;
vector<pair<int, double>> adj[N];
int n, m, case_cnt;
bool vis[N];
double dis[N];
void spfa()
{
  memset(dis, 0, sizeof dis);
  memset(vis, 0, sizeof vis);
  dis[1] = 1;
  queue<int> q;
  q.push(1), vis[1] = true;
  while (!q.empty())
  {
    if (dis[1] > 1) // 发现已经能套利了提前return
      return;
    auto u = q.front();
    q.pop(), vis[u] = false;
    for (auto [v, w] : adj[u])
    {
      if (dis[v] < dis[u] * w)
      {
        dis[v] = dis[u] * w;
        if (!vis[v])
          q.push(v), vis[v] = true;
      }
    }
  }
}
int main() 
{
  cin.tie(nullptr)->sync_with_stdio(false);
  while (cin >> n, n != 0)
  {
    case_cnt++;
    ump = {};
    for (int i = 1; i <= n; i++)
    {
      string name;
      cin >> name;
      ump[name] = i;
      adj[i].clear();
    }
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
      string name_u, name_v;
      int u, v;
      double w;
      cin >> name_u >> w >> name_v;
      u = ump[name_u], v = ump[name_v];
      adj[u].push_back({v, w});

    }
    spfa();
    cout << "Case " << case_cnt << ": " << (dis[1] > 1 ? "Yes" : "No") << '\n';
  }

  return 0;
}