Submission #391947

#	Time	Username	Problem	Language	Result	Execution time	Memory
391947		Jarif_Rahman	Alias (COCI21_alias)	C++17	70 / 70	8 ms	8356 KiB

alias

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e18;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    int wr = 0;
    vector<vector<pair<int, ll>>> v(n);
    map<str, int> index;
    vector<vector<ll>> dis(n, vector<ll>(n, inf));
    for(int i = 0; i < m; i++){
        str sa, sb; ll w; cin >> sa >> sb >> w;
        if(index.find(sa) == index.end()) index[sa] = wr++;
        if(index.find(sb) == index.end()) index[sb] = wr++;
        int a = index[sa], b = index[sb];
        v[a].pb({b, w});
    }
    for(int nd = 0; nd < n; nd++){
        priority_queue<pair<ll, int>> pq;
        vector<bool> bl(n, 0);
        dis[nd][nd] = 0;
        pq.push({0, nd});
        while(!pq.empty()){
            int nd0 = pq.top().sc;
            pq.pop();
            if(bl[nd0]) continue;
            bl[nd0] = 1;
            for(auto [x, w]: v[nd0]) if(dis[nd][nd0]+w < dis[nd][x]){
                dis[nd][x] = dis[nd][nd0]+w;
                pq.push({-dis[nd][x], x});
            }
        }
    }
    int q; cin >> q;
    while(q--){
        str sa, sb; cin >> sa >> sb;
        int a = index[sa], b = index[sb];
        if(dis[a][b] >= inf) cout << "Roger\n";
        else cout << dis[a][b] << "\n";
    }
}

• Subtask 1: 70 / 70