Submission #397605

#	Time	Username	Problem	Language	Result	Execution time	Memory
397605		MrRobot_28	Alias (COCI21_alias)	C++17	70 / 70	8 ms	8268 KiB

alias

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define int long long
#define sz(a) (int)a.size()
const int mod = 998244353;

signed main()
{
  //  ifstream cin("input1.txt.4c");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    map <string, int> mp;
    vector <pair <int, int> > g[n];
    int dist[n][n];
    int it = 0;
    for(int i = 0; i < m; i++)
    {
        string a, b;
        cin >> a >> b;
        int t;
        cin >> t;
        if(mp.count(a) == 0)
        {
            mp[a] = it++;
        }
        if(mp.count(b) == 0)
        {
            mp[b] = it++;
        }
        g[mp[a]].push_back({mp[b], t});
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            dist[i][j] = 1e18;
        }
        dist[i][i] = 0;
        priority_queue <pair <int, int> > q;
        q.push({0, i});
        while(sz(q) != 0)
        {
            int v = q.top().Y;
            int d = -q.top().X;
            q.pop();
            if(d != dist[i][v])
            {
                continue;
            }
            for(auto to : g[v])
            {
                if(dist[i][to.X] > d + to.Y)
                {
                    dist[i][to.X] = d + to.Y;
                    q.push({-dist[i][to.X], to.X});
                }
            }
        }
    }
    int q;
    cin >> q;
    while(q--)
    {
        string a, b;
        cin >> a >> b;
        if(dist[mp[a]][mp[b]] == 1e18)
        {
            cout << "Roger\n";
        }
        else{
            cout << dist[mp[a]][mp[b]] << "\n";
        }
    }
    return 0;
}

• Subtask 1: 70 / 70