oj.uz

Submission #682631

# Submission time Handle Problem Language Result Execution time Memory
682631 2023-01-16T16:05:03 Z Alex_tz307 Alias (COCI21_alias) C++17
70 / 70
 21 ms 468 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 13 ms 468 KB Output is correct
4 Correct 21 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct