fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define what_is(x) cerr << #x << " is " << x << endl;
  4. #define IOS ios::sync_with_stdio(false); cin.tie(0);
  5. #define st first
  6. #define nd second
  7.  
  8. typedef long long ll;
  9. typedef pair<int,int> pii;
  10. const int N = 200+5;
  11. const int INF = 1e9;
  12. const int MOD = 1e9+7;
  13.  
  14. int n, m;
  15. int a[N];
  16. int main()
  17. {
  18. IOS
  19. // freopen("input.txt", "r", stdin);
  20. // freopen("output.txt", "w", stdout);
  21. int tc = 1;
  22. while(cin >> n){
  23. for(int i=1; i<=n; i++) cin >> a[i];
  24. vector<tuple<int,int,int>> edges;
  25. vector<int> g[n+2];
  26. cin >> m;
  27. while(m--){
  28. int u, v; cin >> u >> v;
  29. edges.push_back({u, v, pow(a[v]-a[u], 3)});
  30. g[u].push_back(v);
  31. }
  32. vector<int> d(n+2, INF);
  33. d[1] = 0; //source 1
  34. for(int i=1; i<=n-1; i++){
  35. for(auto e:edges){
  36. int u, v, w; tie(u, v, w) = e;
  37. // what_is(u); what_is(v); what_is(w);
  38. if (d[u] == INF) continue;
  39. d[v] = min(d[v], d[u]+w);
  40. }
  41. }
  42.  
  43. for(auto e:edges){
  44. int u, v, w; tie(u, v, w) = e;
  45. if (d[u] == INF) continue;
  46. if (d[u] + w < d[v]) {
  47. d[v] = -INF;
  48. }
  49. }
  50. int q; cin >> q;
  51. cout << "Set #" << tc++ << endl;
  52. while(q--){
  53. int des; cin >> des;
  54. if (d[des] < 3 || d[des] == INF) cout << "?" << endl;
  55. else cout << d[des] << endl;
  56. }
  57. }
  58.  
  59. return 0;
  60. }
  61.  
Success #stdin #stdout 0s 4324KB
stdin
Standard input is empty
stdout
Standard output is empty