Submission #386870

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
386870	2021-04-07T14:27:55 Z	phathnv	Alias (COCI21_alias)	C++11	70 / 70	9 ms	8428 KB

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.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	4 ms	620 KB	Output is correct
4	Correct	6 ms	876 KB	Output is correct
5	Correct	8 ms	7532 KB	Output is correct
6	Correct	8 ms	7532 KB	Output is correct
7	Correct	9 ms	8428 KB	Output is correct