# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
517665 | ivls | Alias (COCI21_alias) | C++14 | 150 ms | 7628 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n, m;
map<string, int> nn;
vector<int> g[5000];
int dst[5000][5000];
int dist(int st, int fi) {
int dist[5000] = {};
set<pair<int, int>> s;
for (int i = 1; i <= n; i++) {
s.insert(make_pair((i == st ? 0 : 2000000000), i));
dist[i] = (i == st ? 0 : 2000000000);
}
while (!s.empty()) {
int r = (*s.begin()).first, v = (*s.begin()).second;
s.erase(s.begin());
for (int u : g[v]) {
if (dist[u] > dist[v] + dst[v][u]) {
s.erase(make_pair(u, dist[u]));
s.insert(make_pair(u, dist[v] + dst[v][u]));
dist[u] = dist[v] + dst[v][u];
}
}
}
return dist[fi] == 2000000000 ? -1 : dist[fi];
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
int ii = 0;
for (int i = 0; i < m; i++) {
string u, v;
cin >> u >> v;
int t;
cin >> t;
if (nn[u] == 0) {
nn[u] = ++ii;
}
if (nn[v] == 0) {
nn[v] = ++ii;
}
g[nn[u]].push_back(nn[v]);
dst[nn[u]][nn[v]] = t;
}
int qq;
cin >> qq;
while (qq--) {
string a, b;
cin >> a >> b;
if (nn[a] == 0) {
nn[a] = ++ii;
}
if (nn[b] == 0) {
nn[b] = ++ii;
}
int r = dist(nn[a], nn[b]);
if (r == -1) {
cout << "Roger" << '\n';
}
else {
cout << r << '\n';
}
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |