oj.uz

Submission #942514

# Submission time Handle Problem Language Result Execution time Memory
942514 2024-03-10T19:18:25 Z vjudge1 Alias (COCI21_alias) C++17
70 / 70
 284 ms 604 KB 
#include <bits/stdc++.h>

using namespace std;

using ld = long double;
using ll = long long;

#define int ll

#define sz(x) (int)x.size()

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    map<string,vector<pair<string,int>>> adj;

    for(int i=0; i<m; ++i){
        string u, v;
        int w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    map<string,int> dis;

    auto bfs = [&](string u) -> void {
        dis.clear();
        priority_queue<pair<int,string>, vector<pair<int,string>>, greater<pair<int,string>>> pq;
        pq.push({0, u});
        dis[u] = 0;
        while(sz(pq)){
            auto [curCost, curNode] = pq.top();
            pq.pop();

            if(curCost != dis[curNode]) continue;

            for(auto [toNode, toCost] : adj[curNode]){
                if(dis.count(toNode) == 0 or curCost + toCost < dis[toNode]){
                    dis[toNode] = curCost + toCost;
                    pq.push({dis[toNode], toNode});
                }
            }
        }
    };

    int q;
    cin >> q;
    while(q--){
        string u, v;
        cin >> u >> v;

        bfs(u);

        if(dis.count(v) == 0){
            cout << "Roger" << endl;
        } else {
            cout << dis[v] << endl;
        }

    }

}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 199 ms 604 KB Output is correct
4 Correct 284 ms 604 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 7 ms 604 KB Output is correct
7 Correct 4 ms 604 KB Output is correct