Submission #515049

#	Time	Username	Problem	Language	Result	Execution time	Memory
515049		MilosMilutinovic	Alias (COCI21_alias)	C++14	50 / 70	32 ms	588 KiB

alias

#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<int, int>> st;
    vector<int> dist(n, 1e9);
    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]] == 1e9) {
      cout << "Roger" << '\n';
    } else {
      cout << dist[val[t]] << '\n';
    }
  }
  return 0;
}

• Subtask 1: 50 / 70