Na ficção científica, a viagem entre diferentes universos, é feita através de portais ou buracos de minhocas que conectam mundos diferentes ou até mesmo dimensões diferentes.

Imagine que você é um físico renomado que descobriu “buracos de minhocas” (rotas) que permitem o deslocamento entre universos. De acordo com sua descoberta, Todas as rotas são unidirecionais, ou seja, uma rota do universo A para o universo B não implica existência de uma rota do universo B para o universo A.

Mesmo quando existam rotas nos dois sentidos, elas são distintas e não possuem necessariamente a mesma distância (medidas em unidades de espaço-tempo).

O objetivo deste desafio é ajudar futuros viajantes a navegar entre os universos gastando a menor quantidade de espaço-tempo possível. Seu software deverá ser capaz de calcular o custo de deslocamento entre rotas, os números diferentes de rotas entre universos e as rotas mais econômicas.

Os universos e as rotas correspondem respectivamente aos vértices e arestas ponderadas do grafo abaixo:

Seu código deverá resolver os seguintes problemas:

• A distância de A a C passando por B?
• A distância entre A e D?
• A distância de A a C passando por D?
• O número de rotas saindo de C e voltando a C com no máximo 3 paradas?
• O número de rotas entre A e C com no máximo 4 paradas?
• A menor rota (em espaço-tempo) entre A e C?
• A menor rota (em espaço-tempo) saindo de B e voltando a B?
• O número de diferentes rotas saindo de C e voltando a C com distância máxima de 300 unidades de espaço-tempo?

A forma de entrada e saída dos dados fica a sua escolha.

Pedimos que você leia atentamente as instruções abaixo e crie uma solução de código usando Java, JavaScript, Ruby, ou Pyhton.

• Faça a cópia do repositório (fork), desenvolva e submeta uma solicitação de mudança (pull request) no branch master.
• Em caso de dúvidas basta abrir uma issue com sua pergunta (aqui mesmo no github) que nossa equipe irá respondê-lo assim que possível.
• Você não poderá usar bibliotecas externas ou ferramentas resolver o problema das rotas/grafo.
• Não será permitido o uso de bancos de dados orientedos a grafos.
• Avaliaremos uma variedade de aspectos, como design da solução, orientação a objeto, complexidade do código e a existência de testes unitários.
• Esperamos que você encaminhe um código que acredite ter qualidade, que possa ser executado e evoluído.
• Caso deseje evoluir a ideia seguindo essa base, fique à vontade: por exemplo, adaptar as entradas e saídas para ser um serviço web, criar uma interface gráfica, etc.

• Envie as instruções para execução do código
• De preferência, utilize um ferramenta como gradle, maven, npm ou yarn para realizar as tarefas necessárias de build.