Submission #943772

# Submission time Handle Problem Language Result Execution time Memory
943772 2024-03-11T21:11:17 Z vjudge1 Alias (COCI21_alias) C++17
40 / 70
357 ms 656 KB
#include<bits/stdc++.h>
using namespace std;

int INF=99999999;
void dijkstra(vector<vector<pair<int, int> > > &grafo,int origen,vector<int> &distancias)
{
    int n=grafo.size();
    vector<bool> visitados(n,false);
    distancias[origen]=0;
    for(int i=0;i<n;i++)///recorrer todos los nodos
    {
        int minNodo=-1,minDist=INF;
        for(int j=0;j<n;j++)
        {
            if(!visitados[j] && distancias[j]<minDist)
            {
                minDist=distancias[j];
                minNodo=j;
            }

        }
        if(minNodo==-1) break;
        visitados[minNodo]=true;
        for(int a=0;a<grafo[minNodo].size();a++)
        {
            int hacia=grafo[minNodo][a].first;
            int peso=grafo[minNodo][a].second;
            if(!visitados[hacia] && distancias[minNodo]+peso<distancias[hacia])
            {
                distancias[hacia]=distancias[minNodo]+peso;
            }
        }

    }

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    string x,y;
    long long t;
    map<string,vector<pair<string,long long> > >db;
    for(int i=0;i<m;i++){
        cin>>x>>y>>t;
        db[x].push_back(make_pair(y,t));
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        cin>>x>>y;
        map<string,long long>dist;
        queue<string>qu;
        dist[x]=0;
        qu.push(x);
        while(!qu.empty()){
            string next=qu.front();
            qu.pop();
            vector<pair<string,long long> >conexiones=db[next];
            for(int j=0;j<conexiones.size();j++){
                string recuerdo=conexiones[j].first;
                long long tiempo=conexiones[j].second;
                if(dist.count(recuerdo)==0){
                    dist[recuerdo]=dist[next]+tiempo;
                    qu.push(recuerdo);
                }
                else dist[recuerdo]=min(dist[recuerdo],dist[next]+tiempo);
            }
        }
        if(dist.count(y))cout<<dist[y]<<"\n";
        else cout<<"Roger\n";
    }
    return 0;
}

Compilation message

alias.cpp: In function 'void dijkstra(std::vector<std::vector<std::pair<int, int> > >&, int, std::vector<int>&)':
alias.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int a=0;a<grafo[minNodo].size();a++)
      |                     ~^~~~~~~~~~~~~~~~~~~~~~
alias.cpp: In function 'int main()':
alias.cpp:61:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::__cxx11::basic_string<char>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for(int j=0;j<conexiones.size();j++){
      |                         ~^~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 500 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 298 ms 348 KB Output isn't correct
4 Incorrect 357 ms 548 KB Output isn't correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 3 ms 656 KB Output is correct