esse é um problema complexo, no modelo de problemas apresentados em "maratonas de programação", e servidores de problemas on line no modelo do SPOJ -
O mais importante é, antes de escrever o código, entender os dados que você tem e como vai modelar isso com as estrutura de dados comuns do Python (dicionários, listas e conjuntos) - e até se vale a pena criar uma classe especializada
para alguma das abstrações do problema (terminais, ou linhas de ônibus).
Daí, pode dar nomes melhores para as variáveis, por que o cérebro funciona melhor com "num_linhas" do que com "L" - mesmo que fique 2% mais fácil, é um 2% que se multiplica em cada linha do seu programa. Os nomes de variáveis curtos são uma característica histórica de problemas de programação criados em um ambiente acadêmico, em que a linguagem matemática é muito forte - mas não ajudam na forma como as ferramentas modernas trabalham.
Quanto ao problema em si:
podemos de fato ter dois dicionários - um com as linhas de ônibus, onde cada "valor" é um conjunto (set) (se não conhecer os set
, para esse efeito são parecidos com listas, mas mais eficientes já que a ordem não importa) - e cada entrada no set
a chave de um dos terminais de ônibus.
A segunda estrutura que vai ajudar é um dicionario "ao contrário" - onde as chaves são o identificador dos terminais, e os valores conjuntos com os identificadores das linhas de ônibus que passam por lá.
Agora pensar em como resolver o problema:
Se o maior número de pulos entre um terminal e outro fosse sempre "0" - o ônibus passa no terminal desejado, o problema seria trivial - só pegar o terminal escolhido para início (0), e tomar qualquer ônibus que passe no terminal destino (1).
Mas e aí, quando nenhum dos ônibus terminal de início passa no terminal destino?
Seguinte: para cada terminal onde cada ônibus que sai do terminal (0) temos que repetir a análise - (estamos no caso trivial? se sim chegamos, senão, verificar todos os terminais possíveis a partir de cada ponto onde o ônibus passa) -
é fácil ver que é um problema que requer uma chamada recursiva - "veja onde cada ônibus daqui passa - se passa no terminal destino chegou - senão veja repita a busca a partir de cada terminal onde cada ônibus saindo daqui passa" - para evitar laços infinitos, aqui vai o pulo do gato: a medida que o problema é "desvendado", o número mínimo de linhas de onibus entre cada par de terminais vai sendo anotado em um terceiro dicionário. Daí - a função recursiva só precisa ser chamada novamente para pares de terminais onde ainda não verificou a distância.
Assim - vamos supor que vamos do terminal 0 para o 1. Não tem ônibus direto - analisamos a rota do ônibus A - ele passa nos terminais 2, 5, 7 - e aí verificamos que já existe a distância entre o terminal "7" e o "1" que é o destino, por que há um ônibus direto - pronto o número de ônibus entre 0 e 1 é "1" + a distância entre "7 e "1" - (e já anotamos isso no dicionário de distâncias).
Uma outra ferramenta muito bacana que o Python tem aí, que o autor do problema provavelmente nem previu que teriamos pronta é o frozenset
- isso é como se fosse uma "tupla", mas sem ordem específica - e pode ser usado como chave do dicionário que acha as distâncias entre as cidades - e vai funcionar tanto para a chave "0, 1" como para a ordem contrária "1, 0". .
Antes de escrever algum código com mais dicas de como implementar isso, vou dar uma olhada no seu código e comentar alguma coisa:
T, L, O, D = map(int, input().split())
terminais_por_linha = {}
linhas_por_terminal = {}
OK - até aqui, você tem a entrada de dados da primeira linha - e criação das
estruturas de dados - as mesmas que indiquei que são necessárias.
for i in range(1, L+1):
terminais_por_linha[i] = list(input().split())
del(terminais_por_linha[i][0])
Aqui, ok - você lê cada linha descrevendo as linhas de ônibus, descarta
o primeiro número que não é necessário em Python - já que as listas
e conjuntos tem um número dinâmico. Você não converte o número de cada
terminal pra inteiro - não faz diferença desde que lembremos que são strings em
todo o problema.
for i in range(1, T+1):
linhas_por_terminal[i] = []
Aqui já tem um problema -você inicializa o segundo dicionário, mas
deixa ele "em branco" - vamos precisar que a informação de quais linhas
passam em cada terminal seja preenchida.
for k in range(1, T+1):
for i in range(len(terminais_por_linha)):
for j in range(len(terminais_por_linha[i+1])):
if int(terminais_por_linha[i+1][j]) == k:
linhas_por_terminal[k].append(i+1)
Ok - aqui você tenta preencher essa estrutura de dados - das linhas que passam em cada terminal - de forma bastante ineficiente - e, cuidado - ao misturar o "range" que começa em "0" com as chavs que são os números dos terminais e das linhas que começam em "1", você começa a por esses "+ 1" ai no meio - a chance desses '+ 1'se desencontrarem é de quase 100% - mesmo que todo o restante do código esteja certo.
E -- acabou o seu código - você nem chega a tentar resolver de fato o problema -
acredito até que esse último bloco funcione.
Então vamos lá
Funções!
Regra número zero: mesmo que não vá precisar, ou pense que não
vá precisar, sempre divida seu programa em funções.
Senão, acaba acontecendo o que já estava contaminando o seu código: a lógica
da entrada dos dados vai escorregando e se misturando a lógica do programa.
DIsto isso, vamos acertar a entrada de dados - e tendo os dois dicionários preenchidos, implementar uma função que busque "dados dois terminais há um
ônibus direto de um para outro?" E ai uma outra que faça: "para um ônibus, veja em cada terminal onde ele para, quais tem distância zero?" (essa função vai dar os terminais de distância "1") - daí, tornando-a recursiva, podemos achar qualquer distância entre dois terminais.
def entrada(terminais_por_linha, linhas_por_terminal):
T, L, O, D = [int(elemento) for elemento in input().split()]
for i in range(1, L+1):
# 'set' em vez de 'list' para as informações permite algumas operações mais eficientes.
terminais_por_linha[i] = set(list(int(terminal) for terminal in input().split())[1:])
for linha, terminais in terminais_por_linha.items():
for terminal in terminais:
# o método "setdefault" de dicionários é o mesmo que
# "se a chave não existe, crie a chave com o valor passado,
# e retorne aquele valor, se a chave existe, retorne o seu valor"
linhas_por_terminal.setdefault(terminal, set()).add(linha)
# Os dicionários são alterados "in place": isso é - permanecem
# os mesmos objetos, e são alimentados com os valores da entrada,
# então não precisam ser retornados
return T, L, O, D
def saida(resultado):
# Nunca misturar a entrada e saída em itneração com o usuário
# com a logica do programa. Desta forma, a mesma lógica
# do programa pode ser usada se for criado uma versão web
# ou em um aplicativo em janelas do programa
print(resultado)
def checa_distancia_um(terminais_por_linha, linhas_por_terminal, t1):
"""retorna um conjunto com todos os terminais a distância "1" do terminal passado"""
resultados = set()
for linha in linhas_por_terminal(t1):
resultados.update(terminais_por_linha[linha])
return resultados
def checa_distancia(terminais_por_linha, linhas_por_terminal, cache_de_distancias, t1, t2):
# continua
chave = frozenset({t1, t2})
if chave in cache_de_distancias:
return cache_de_distancias[chave]
if t1 == t2:
cache_de_distancias[chave] = 0
elif t2 in checa_distancia_um(terminais_por_linha, linhas_por_terminal, t1):
cache_de_distancias[chave] = 1
else:
distancias = []
for linha in linhas_por_terminal[t1]:
for terminal in terminais_por_linha[linha]:
if terminal == t1:
continue # não verificar o terminal inicial
dist = checa_distancia(terminais_por_linha, linhas_por_terminal, terminal, t2)
if dist != None:
distancias.append(dist)
if not distancias:
# não há conexão entre t1 e t2:
return None
# retorna a menos distância encontrada, acrescida de um passo
# (que são as paradas do onibus saindo de t1)
cache_de_distancias[chave] = min(distancias) + 1
return cache_de_distancias[chave]
def principal():
terminais_por_linha = {}
linhas_por_terminal = {}
cache_de_distancias = {}
numero_terminais, numero_linhas, origem, destino = entrada(terminais_por_linha, linhas_por_terminal)
resultado = checa_distancia(terminais_por_linha, linhas_por_terminal, cache_de_distancias)
saida(resultado)
principal()
(Ainda não testei, mas a ideia é essa - você tem algum conjunto de dados de teste aí?)