Submission #386869

# Submission time Handle Problem Language Result Execution time Memory
386869 2021-04-07T14:25:19 Z phathnv Alias (COCI21_alias) C++11
0 / 70
9 ms 8428 KB
#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;
    for(int i = 1; i <= m; i++){
        string a, b;
        int t;
        cin >> a >> b >> t;
        if (wordInd.find(a) == wordInd.end())
            wordInd[a] = wordInd.size();
        if (wordInd.find(b) == wordInd.end())
            wordInd[b] = wordInd.size();
        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;
}
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Incorrect 4 ms 620 KB Output isn't correct
4 Incorrect 6 ms 876 KB Output isn't correct
5 Incorrect 8 ms 7532 KB Output isn't correct
6 Incorrect 8 ms 7532 KB Output isn't correct
7 Incorrect 9 ms 8428 KB Output isn't correct