Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- #define ii pair<int, int>
- #define vi vector<int>
- #define vl vector<ll>
- #define pb push_back
- #define mp make_pair
- #define ff first
- #define ss second
- #define prime 1000000007
- #define all(v) v.begin(), v.end()
- #define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- #define EPS (1e-8)
- int oo = (1e9) + 7;
- ll oo2 = 1ll * oo * oo;
- #define W(x) cerr << "\033[33m" << #x << " = " << x << "\033[0m" << "\n";
- #define forn(i, n) for (int i = 0; i < int(n); i++)
- using namespace std;
- vector<ll> dijkstra(int start, const vector<vector<pair<int, ll>>> &g) {
- vector<ll> d(30, oo2);
- priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
- d[start] = 0;
- pq.emplace(0, start);
- ll dt, w;
- int u, v;
- while (!pq.empty()) {
- tie(dt, u) = pq.top();
- pq.pop();
- if (dt > d[u]) continue;
- for (auto edge : g[u]) {
- tie(v, w) = edge;
- if (d[v] > d[u] + w) {
- d[v] = d[u] + w;
- pq.emplace(d[v], v);
- }
- }
- }
- return d;
- }
- int main() {
- FIO
- int n, p;
- char t, d, a, b, startA, startD;
- vector<vector<pair<int, ll>>> go(30), gt(30);
- cin >> n;
- for (int i = 0; i < n; i++) {
- cin >> t >> d >> a >> b >> p;
- if (t == 'O') {
- go[a-'A'].push_back({b - 'A', p});
- if (d == 'B') {
- go[b].push_back({a - 'A', p});
- }
- }
- else {
- gt[a-'A'].push_back({b - 'A', p});
- if (d == 'B') {
- gt[b-'A'].push_back({a - 'A', p});
- }
- }
- }
- cin >> startA >> startD;
- vector<ll> distA = dijkstra(startA - 'A', go);
- vector<ll> distB = dijkstra(startD - 'A', gt);
- ll wans = oo2;
- vector<char> ans;
- for (int i = 0; i < 26; i++) {
- if (distA[i] + distB[i] <= wans) {
- wans = distA[i] + distB[i];
- }
- }
- for (int i = 0; i < 26; i++) {
- if (distA[i] + distB[i] == wans) {
- ans.emplace_back(i + 'A');
- }
- }
- if (wans == oo2) {
- cout << -1 << '\n';
- }
- else {
- sort(all(ans));
- cout << wans << '\n';
- for (auto x : ans) {
- cout << x << " ";
- }
- cout << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement