fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pep_Guardiola      \
  3.   ios::sync_with_stdio(0); \
  4.   cin.tie(0);              \
  5.   cout.tie(0);
  6. using namespace std;
  7. const long double eps = 1e-9;
  8. int t = 1;
  9. struct Edge
  10. {
  11.   int u, v;
  12.   long double w;
  13.   Edge(int u, int v, long double w) : u(u), v(v), w(w) {}
  14.   Edge() = default;
  15. };
  16. int main(void)
  17. {
  18.   pep_Guardiola int n;
  19.   while (cin >> n)
  20.   {
  21.     if (!n)
  22.       break;
  23.     int id = 0;
  24.     map<string, int> mp;
  25.     for (int i = 0; i < n; i++)
  26.     {
  27.       string s;
  28.       cin >> s;
  29.       mp[s] = id++;
  30.     }
  31.     int m;
  32.     cin >> m;
  33.     vector<Edge> a(m);
  34.     for (int i = 0; i < m; i++)
  35.     {
  36.       string s, t;
  37.       long double w;
  38.       cin >> s >> w >> t;
  39.       a[i] = Edge(mp[s], mp[t], w);
  40.     }
  41.  
  42.     function<bool(int)> go = [&](int src) -> bool
  43.     {
  44.       vector<long double> dist(id + 1, 0.0);
  45.       dist[src] = 1.0;
  46.       function<bool(int, int, long double)> relax = [&](int u, int v, long double w) -> bool
  47.       { return ((dist[u] * w) > dist[v] + eps) ? (dist[v] = dist[u] * w, true) : false; };
  48.       for (int i = 0; i < n; i++)
  49.         for (auto &[u, v, w] : a)
  50.           relax(u, v, w);
  51.       return dist[src] > (1.0 + eps);
  52.     };
  53.     bool ok = 0;
  54.     for (int i = 0; i < id; i++)
  55.       ok |= (go(i));
  56.     cout << "Case " << t++ << ": " << (ok ? "Yes\n" : "No\n");
  57.   }
  58. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ytTCiy
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!