oj.uz

Submission #966733

# Submission time Handle Problem Language Result Execution time Memory
966733 2024-04-20T09:15:56 Z AliHasanli Alias (COCI21_alias) C++17
70 / 70
 49 ms 860 KB 
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,long long>>g[1001];
bool used[1001];
long long dist[1001];
void dijkstra(int source)
{
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pq;
    pq.push({0,source});
    while(pq.size())
    {
        long long cost=pq.top().first;
        int node=pq.top().second;
        pq.pop();
        if(used[node])continue;
        used[node]=1;
        dist[node]=cost;
        for(pair<int,long long>go:g[node])
        {
            if(used[go.first])continue;
            pq.push({go.second+cost,go.first});
        }
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    set<string>s;
    vector<pair<string,pair<string,long long>>>v;
    for(int i=0;i<m;i++)
    {
        string a,b;
        long long c;
        cin>>a>>b>>c;
        v.push_back({a,{b,c}});
        s.insert(a);
        s.insert(b);
    }
    map<string,int>mp1;
    int ii=1;
    for(string i:s)mp1[i]=ii,ii++;
    for(pair<string,pair<string,long long>>i:v)
        g[mp1[i.first]].push_back({mp1[i.second.first],i.second.second});
    int q;
    cin>>q;
    while(q--)
    {
        for(int i=0;i<1001;i++)dist[i]=1000000000000000000,used[i]=0;
        string s,e;
        cin>>s>>e;
        dijkstra(mp1[s]);
        if(dist[mp1[e]]==1000000000000000000)cout<<"Roger"<<endl;
        else cout<<dist[mp1[e]]<<endl;
    }
    return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 49 ms 604 KB Output is correct
4 Correct 46 ms 604 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 7 ms 856 KB Output is correct
7 Correct 5 ms 860 KB Output is correct