Submission #943773

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
943773	2024-03-11T21:13:04 Z	vjudge1	Alias (COCI21_alias)	C++17	40 / 70	363 ms	640 KB

alias

#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;
                    if(recuerdo!=y)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++){
      |                         ~^~~~~~~~~~~~~~~~~~

Subtask #1

40.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Incorrect	1 ms	348 KB	Output isn't correct
3	Incorrect	292 ms	600 KB	Output isn't correct
4	Incorrect	363 ms	552 KB	Output isn't correct
5	Correct	5 ms	640 KB	Output is correct
6	Correct	4 ms	604 KB	Output is correct
7	Correct	3 ms	604 KB	Output is correct