Advertisement
Guest User

Untitled

a guest
Nov 17th, 2019
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.18 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define ii pair<int, int>
  5. #define vi vector<int>
  6. #define vl vector<ll>
  7. #define pb push_back
  8. #define mp make_pair
  9. #define ff first
  10. #define ss second
  11. #define prime 1000000007
  12. #define all(v) v.begin(), v.end()
  13. #define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  14. #define EPS (1e-8)
  15.  
  16. int oo = (1e9) + 7;
  17. ll oo2 = 1ll * oo * oo;
  18.  
  19. #define W(x) cerr << "\033[33m" << #x << " = " << x << "\033[0m" << "\n";
  20. #define forn(i, n) for (int i = 0; i < int(n); i++)
  21.  
  22. using namespace std;
  23.  
  24. vector<ll> dijkstra(int start, const vector<vector<pair<int, ll>>> &g) {
  25. vector<ll> d(30, oo2);
  26.  
  27. priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
  28. d[start] = 0;
  29. pq.emplace(0, start);
  30.  
  31. ll dt, w;
  32. int u, v;
  33. while (!pq.empty()) {
  34. tie(dt, u) = pq.top();
  35. pq.pop();
  36.  
  37. if (dt > d[u]) continue;
  38.  
  39. for (auto edge : g[u]) {
  40. tie(v, w) = edge;
  41. if (d[v] > d[u] + w) {
  42. d[v] = d[u] + w;
  43. pq.emplace(d[v], v);
  44. }
  45. }
  46. }
  47.  
  48. return d;
  49. }
  50.  
  51. int main() {
  52. FIO
  53. int n, p;
  54. char t, d, a, b, startA, startD;
  55. vector<vector<pair<int, ll>>> go(30), gt(30);
  56.  
  57. cin >> n;
  58.  
  59. for (int i = 0; i < n; i++) {
  60. cin >> t >> d >> a >> b >> p;
  61.  
  62. if (t == 'O') {
  63. go[a-'A'].push_back({b - 'A', p});
  64. if (d == 'B') {
  65. go[b].push_back({a - 'A', p});
  66. }
  67. }
  68. else {
  69. gt[a-'A'].push_back({b - 'A', p});
  70. if (d == 'B') {
  71. gt[b-'A'].push_back({a - 'A', p});
  72. }
  73. }
  74. }
  75.  
  76. cin >> startA >> startD;
  77.  
  78. vector<ll> distA = dijkstra(startA - 'A', go);
  79. vector<ll> distB = dijkstra(startD - 'A', gt);
  80.  
  81. ll wans = oo2;
  82. vector<char> ans;
  83. for (int i = 0; i < 26; i++) {
  84. if (distA[i] + distB[i] <= wans) {
  85. wans = distA[i] + distB[i];
  86. }
  87. }
  88.  
  89. for (int i = 0; i < 26; i++) {
  90. if (distA[i] + distB[i] == wans) {
  91. ans.emplace_back(i + 'A');
  92. }
  93. }
  94.  
  95. if (wans == oo2) {
  96. cout << -1 << '\n';
  97. }
  98. else {
  99. sort(all(ans));
  100. cout << wans << '\n';
  101. for (auto x : ans) {
  102. cout << x << " ";
  103. }
  104. cout << '\n';
  105. }
  106.  
  107. return 0;
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement