Submission #682575

#	Time	Username	Problem	Language	Result	Execution time	Memory
682575		vjudge1	Alias (COCI21_alias)	C++17	70 / 70	18 ms	488 KiB

alias

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3;
const int64_t INF = 1e16L;
int n, m;
int64_t dp[N];
vector<pair<int, int>> g[N];

string Dijkstra(int src, int dest) {
  for (int v = 0; v < n; ++v) {
    dp[v] = INF;
  }

  dp[src] = 0;
  priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;
  pq.emplace(0, src);

  while (!pq.empty()) {
    int64_t cost;
    int u;
    tie(cost, u) = pq.top();
    pq.pop();

    if (cost != dp[u]) {
      continue;
    }

    for (const auto &it : g[u]) {
      int v, w;
      tie(v, w) = it;

      if (dp[v] > dp[u] + w) {
        dp[v] = dp[u] + w;
        pq.emplace(dp[v], v);
      }
    }
  }

  if (dp[dest] == INF) {
    return "Roger";
  }

  return to_string(dp[dest]);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;

  unordered_map<string, int> nodes;

  for (int i = 0; i < m; ++i) {
    string u, v;
    int t;
    cin >> u >> v >> t;

    if (nodes.find(u) == nodes.end()) {
      nodes[u] = nodes.size();
    }

    if (nodes.find(v) == nodes.end()) {
      nodes[v] = nodes.size();
    }

    g[nodes[u]].emplace_back(nodes[v], t);
  }

  int q;
  cin >> q;

  for (int i = 0; i < q; ++i) {
    string u, v;
    cin >> u >> v;

    cout << Dijkstra(nodes[u], nodes[v]) << '\n';
  }

  return 0;
}

• Subtask 1: 70 / 70