제출 #942514

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
942514		vjudge1	Alias (COCI21_alias)	C++17	70 / 70	284 ms	604 KiB

alias

#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 / 70