Submission #943770

#	Time	Username	Problem	Language	Result	Execution time	Memory
943770		svaz	Alias (COCI21_alias)	C++17	40 / 70	358 ms	640 KiB

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>q;
        dist[x]=0;
        q.push(x);
        while(!q.empty()){
            string next=q.front();
            q.pop();
            vector<pair<string,long long> >conexiones=db[next];
            for(int i=0;i<conexiones.size();i++){
                string recuerdo=conexiones[i].first;
                long long tiempo=conexiones[i].second;
                if(dist.count(recuerdo)==0){
                    dist[recuerdo]=dist[next]+tiempo;
                    q.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 (stderr)

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 i=0;i<conexiones.size();i++){
      |                         ~^~~~~~~~~~~~~~~~~~

• Subtask 1: 40 / 70