Submission #445450

#	Time	Username	Problem	Language	Result	Execution time	Memory
445450		retsiger	Alias (COCI21_alias)	C++14	70 / 70	22 ms	8440 KiB

alias

#include<bits/stdc++.h>
#define x first
#define y second
#define bug(x) cerr<<#x<<" = "<<x<<'\n'

using namespace std;
using ll = long long;

const int maxn = 1005;
const ll INF = 1e18;

typedef pair <int, int> ii;

int N, M, cn;
map <string, int> num;
vector <ii> G[maxn];
ll D[maxn][maxn];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> N >> M;
  for (int i = 0; i < M; ++i) {
    string u, v; int t;
    cin >> u >> v >> t;
    int x, y;
    if (num[u]) x = num[u];
    else x = num[u] = ++cn;
    if (num[v]) y = num[v];
    else y = num[v] = ++cn;
    G[x].push_back({y, t});
    bug(x);
    bug(y);
  }
  memset(D, 0x7f, sizeof D);
  for (int u = 1; u <= N; ++u) {
    D[u][u] = 0;
    priority_queue <ii, vector<ii>, greater<ii>> q;
    q.push({0, u});
    while (q.size()) {
      ii cur = q.top(); q.pop();
      if (cur.x > D[u][cur.y]) continue;
      int x = cur.y;
      for (auto p : G[x]) {
        int y = p.x, t = p.y;
        if (D[u][y] > D[u][x] + t) {
          D[u][y] = D[u][x] + t;
          q.push({D[u][y], y});
        }
      }
    }
  }
  int q; cin >> q;
  while (q--) {
    string u, v; cin >> u >> v;
    int x = num[u], y = num[v];
    if (D[x][y] > INF) {
      cout << "Roger\n";
    } else
      cout << D[x][y] << '\n';
  }
  return 0;
}

• Subtask 1: 70 / 70