fork download
  1. #include <bits/stdc++.h>
  2.  
  3. #define FE(x, v) for (typeof v.begin() x = v.begin(); x != v.end(); ++x)
  4. #define FOR(i, a, n) for(int i = a; i < (int)n; ++i)
  5. #define REP(i, n) FOR(i, 0, n)
  6. #define el '\n'
  7.  
  8. using namespace std;
  9.  
  10. const int N = 100, oo = 1000000000;
  11. int n, x, y, a, b, g1[N][N], g2[N][N];
  12. string s;
  13. bool v, p;
  14.  
  15. int main() {
  16. ios_base::sync_with_stdio(false); cin.tie(NULL);
  17. while (cin >> n && n) {
  18. REP(i, n) REP(j, n) g1[i][j] = g2[i][j] = (i == j) ? 0 : oo;
  19. if (p) cerr << "Normal:" << el;
  20. REP(nn, n) {
  21. cin >> x; --x;
  22. getline(cin, s);
  23. istringstream iss(s);
  24. while (iss >> y) {
  25. g1[x][--y] = 1;
  26. if (p) cerr << x+1 << "->" << y+1 << ' ';
  27. }
  28. if (p) cerr << el;
  29. }
  30. if (p) cerr << el << "Prop:" << el;
  31. REP(nn, n) {
  32. cin >> x; --x;
  33. getline(cin, s);
  34. istringstream iss(s);
  35. while (iss >> y) {
  36. g2[x][--y] = 1;
  37. if (p) cerr << x+1 << "->" << y+1 << ' ';
  38. }
  39. if (p) cerr << el;
  40. }
  41. if (p) cerr << el;
  42. cin >> a >> b;
  43. REP(k, n) REP(i, n) REP(j, n) {
  44. g1[i][j] = min(g1[i][j], g1[i][k] + g1[k][j]);
  45. g2[i][j] = min(g2[i][j], g2[i][k] + g2[k][j]);
  46. }
  47. v = true;
  48. REP(i, n) {
  49. if (!v) break;
  50. REP(j, n)
  51. if (g2[i][j] > (g1[i][j] * a + b)) {
  52. v = false;
  53. break;
  54. }
  55. }
  56. cout << (v ? "Yes\n" : "No\n");
  57. }
  58. return 0;
  59. }
Success #stdin #stdout 0s 3548KB
stdin
5
1  2  3
2  1  5
3  4  5  1
4  3  5
5  2  3  4
1  2
2  5
3  1  4
4  5
5  3
1  2
5
1  2  3
2  1  5
3  4  5  1
4  3  5
5  2  3  4
1  2
2  5
3  1  4
4  5
5  3
2  0
3
1  2
2  1  3
3  1  2
1  2
2  3
3  1
0  2
0
stdout
Yes
No
Yes