oj.uz

Submission #515050

# Submission time Handle Problem Language Result Execution time Memory
515050 2022-01-19T02:11:57 Z MilosMilutinovic Alias (COCI21_alias) C++14
70 / 70
 37 ms 588 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<string> u(m), v(m);
  vector<int> w(m);
  map<string, int> val;
  int id = 0;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i] >> w[i];
    if (!val.count(u[i])) {
      val[u[i]] = id++;
    }
    if (!val.count(v[i])) {
      val[v[i]] = id++;
    }
    g[val[u[i]]].emplace_back(val[v[i]], w[i]);
  }
  int q;
  cin >> q;
  while (q--) {
    string s, t;
    cin >> s >> t;
    if (!val.count(s)) {
      val[s] = id++;
    }
    if (!val.count(t)) {
      val[t] = id++;
    }
    set<pair<long long, int>> st;
    const long long inf = 1e18;
    vector<long long> dist(n, inf);
    dist[val[s]] = 0;
    st.emplace(0, val[s]);
    while (!st.empty()) {
      int i = st.begin()->second;
      st.erase(st.begin());
      for (auto e : g[i]) {
        int j = e.first;
        int w = e.second;
        if (dist[j] > dist[i] + w) {
          auto it = st.find({dist[j], j});
          if (it != st.end()) {
            st.erase(it);
          }
          dist[j] = dist[i] + w;
          st.emplace(dist[j], j);
        }
      }
    }
    if (dist[val[t]] == inf) {
      cout << "Roger" << '\n';
    } else {
      cout << dist[val[t]] << '\n';
    }
  }
  return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 22 ms 460 KB Output is correct
4 Correct 37 ms 476 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 4 ms 588 KB Output is correct