제출 #619313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
619313		Hussein3602	Alias (COCI21_alias)	C++14	70 / 70	186 ms	3668 KiB

alias

#include<bits/stdc++.h>

using namespace std ;

typedef long long ll ;

const int N=1e5;

int n , m , cnt=1 , q ;

vector< pair<ll,ll> > edges[N] ;

vector<ll>dist(N,-1) ;

map<string,ll>mp ;

ll bfs(int src, int traget)
{
    set < pair<ll,ll> > s ;
    s.insert({0,src}) ;
    while(!s.empty())
    {
        pair<ll,ll> p = *s.begin() ;
        s.erase(p) ;
        ll node=p.second , nodecost=p.first ;
        if(dist[node]!=-1)continue ;
        dist[node]=nodecost;
        for( pair<ll,ll> edge :edges[node])
        {
            s.insert({nodecost+edge.second,edge.first}) ;
        }
    }
    if(dist[traget]!=-1)return dist[traget];
    return -1;
}
int main()
{
    cin >> n >> m ;
    for(int i=0;i<m;i++)
    {
        string x , y ;

        ll t ;

        cin >> x >> y >> t ;

        if(mp[x]==0)mp[x]=cnt++;

        if(mp[y]==0)mp[y]=cnt++;

        edges[mp[x]].push_back({mp[y],t}) ;
    }
    cin >> q ;
    while(q--)
    {
        string x , y ;
        cin >> x >> y ;
        ll d=bfs(mp[x],mp[y]) ;
        if(d==-1)cout<<"Roger"<<endl;
        else cout<<d<<endl;
        for(int i=0;i<=1000;i++)dist[i]=-1;
    }
}

• Subtask 1: 70 / 70