Submission #386870

#	Time	Username	Problem	Language	Result	Execution time	Memory
386870		phathnv	Alias (COCI21_alias)	C++11	70 / 70	9 ms	8428 KiB

alias

#include <bits/stdc++.h>
using namespace std;

const int N = 1007;
const long long INF = 1e18;

struct Edge{
    int u, v, c;
    Edge(int _u, int _v, int _c){
        u = _u;
        v = _v;
        c = _c;
    }
};

int n, m, q;
vector<Edge> adj[N];
long long dist[N][N];

void Dijkstra(int s, long long dist[N]){
    for(int i = 1; i <= n; i++)
        dist[i] = INF;
    typedef pair<long long, int> PqData;
    priority_queue<PqData, vector<PqData>, greater<PqData>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()){
        int u = pq.top().second;
        long long d = pq.top().first;
        pq.pop();
        if (d != dist[u])
            continue;
        for(Edge e : adj[u])
            if (dist[e.v] > dist[u] + e.c){
                dist[e.v] = dist[u] + e.c;
                pq.push({dist[e.v], e.v});
            }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    map<string, int> wordInd;
    int numWord = 0;
    for(int i = 1; i <= m; i++){
        string a, b;
        int t;
        cin >> a >> b >> t;
        if (wordInd.find(a) == wordInd.end())
            wordInd[a] = ++numWord;
        if (wordInd.find(b) == wordInd.end())
            wordInd[b] = ++numWord;
        adj[wordInd[a]].push_back(Edge(wordInd[a], wordInd[b], t));
    }

    for(int i = 1; i <= n; i++)
        Dijkstra(i, dist[i]);
    cin >> q;
    while (q--){
        string a, b;
        cin >> a >> b;
        if (dist[wordInd[a]][wordInd[b]] == INF)
            cout << "Roger\n";
        else
            cout << dist[wordInd[a]][wordInd[b]] << '\n';
    }

    return 0;
}

• Subtask 1: 70 / 70