fork(1) download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long int ll;
  6. typedef unsigned long long int ull;
  7. typedef long double ld;
  8. typedef pair <ll, ll> pll;
  9. typedef pair <int, int> pii;
  10.  
  11. #define pb push_back
  12. #define mp make_pair
  13. #define ff first
  14. #define ss second
  15. #define all(a) a.begin(), a.end()
  16. #define sz(a) (ll)(a.size())
  17. #define endl "\n"
  18.  
  19. ll gcd(ll a, ll b)
  20. {
  21. if(b==0)
  22. {
  23. return a;
  24. }
  25.  
  26. return gcd(b, a%b);
  27. }
  28.  
  29. const ll L = 505;
  30.  
  31. vector <ll> t(L);
  32. vector <ll> f[L];
  33. vector <ll> s[L];
  34. bool visited[L];
  35.  
  36. int main()
  37. {
  38. ios_base::sync_with_stdio(false);
  39. cin.tie(NULL); cout.tie(NULL);
  40.  
  41. ll tc = 0;
  42.  
  43. while(true)
  44. {
  45. tc++;
  46.  
  47. ll v, e;
  48. cin >> v >> e;
  49.  
  50. ll tot = 0;
  51.  
  52. if(!v && !e)
  53. {
  54. break;
  55. }
  56.  
  57. for(ll i=0; i<L; i++)
  58. {
  59. f[i].clear();
  60. s[i].clear();
  61. t[i] = 0;
  62. }
  63.  
  64.  
  65. for(ll i=1; i<=v; i++)
  66. {
  67. cin >> t[i];
  68.  
  69. tot+=t[i];
  70. }
  71.  
  72. for(ll i=0; i<e; i++)
  73. {
  74. ll a, b;
  75. cin >> a >> b;
  76.  
  77. f[a].pb(b);
  78. s[b].pb(a);
  79. }
  80.  
  81. ll q;
  82. cin >> q;
  83.  
  84. cout << "Case #" << tc << ":" << endl;
  85.  
  86. while(q--)
  87. {
  88. ll x;
  89. cin >> x;
  90.  
  91. queue <ll> q1, q2;
  92.  
  93. for(ll i=0; i<L; i++)
  94. {
  95. visited[i] = false;
  96. }
  97.  
  98. q1.push(x);
  99. q2.push(x);
  100.  
  101. ll sum1 = 0, sum2 = 0;
  102.  
  103. while(!q1.empty())
  104. {
  105. ll top = q1.front();
  106. q1.pop();
  107.  
  108. sum1+=t[top];
  109.  
  110. visited[top] = true;
  111.  
  112. for(auto i: f[top])
  113. {
  114. if(!visited[i])
  115. {
  116. q1.push(i);
  117. }
  118. }
  119. }
  120.  
  121. while(!q2.empty())
  122. {
  123. ll top = q2.front();
  124. q2.pop();
  125.  
  126. sum2+=t[top];
  127.  
  128. visited[top] = true;
  129.  
  130. for(auto i: s[top])
  131. {
  132. if(!visited[i])
  133. {
  134. q2.push(i);
  135. }
  136. }
  137. }
  138.  
  139. cout << tot - sum1 - sum2 + t[x] << endl;
  140. }
  141.  
  142. cout << endl;
  143. }
  144.  
  145. return 0;
  146. }
Success #stdin #stdout 0s 15264KB
stdin
4 4
4 3 2 1
2 1
2 4
3 1
3 4
2
1 2

4 4
4 3 2 1
2 1
2 4
3 1
3 4
2
3 4

0 0
stdout
Case #1:
1
2

Case #2:
3
4