oj.uz

Submission #682575

# Submission time Handle Problem Language Result Execution time Memory
682575 2023-01-16T14:36:47 Z vjudge1 Alias (COCI21_alias) C++17
70 / 70
 18 ms 488 KB 
#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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 12 ms 340 KB Output is correct
4 Correct 18 ms 360 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 488 KB Output is correct
7 Correct 2 ms 468 KB Output is correct