제출 #386343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
386343		model_code	Alias (COCI21_alias)	C++17	70 / 70	52 ms	512 KiB

alias

#include <map>
#include <set>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;

const int maxn = 1005;

int cnt;
map<string, int> ind_map;

int ind(string x) {
    if (ind_map.find(x) == ind_map.end())
        ind_map[x] = cnt++;
    return ind_map[x];
}

int n, m, q;
vector<pii> e[maxn];

ll dist[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int t;
        string x, y;
        cin >> x >> y >> t;
        e[ind(x)].push_back(pii(ind(y), t));
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        string x, y;
        cin >> x >> y;
        set<pli> s;
        memset(dist, -1, sizeof dist);
        dist[ind(x)] = 0;
        s.insert(pli(0, ind(x)));
        while (!s.empty()) {
            pli curr = *s.begin();
            s.erase(curr);
            int curr_ind = curr.second;
            for (int j = 0; j < (int)e[curr_ind].size(); j++) {
                int nxt = e[curr_ind][j].first;
                int d = e[curr_ind][j].second;
                if (dist[nxt] == -1 || dist[nxt] > dist[curr_ind] + d) {
                    s.erase(pli(dist[nxt], nxt));
                    dist[nxt] = dist[curr_ind] + d;
                    s.insert(pli(dist[nxt], nxt));
                }
            }
        }
        if (dist[ind(y)] == -1)
            cout << "Roger" << endl;
        else
            cout << dist[ind(y)] << endl;
    }
    return 0;
}

• Subtask 1: 70 / 70