Museu

Desde que o arquiteto Frank Gehry projetou o Museu Guggenheim de Bilbao, os museus têm sido construídos com formas cada vez mais complexas, fugindo de padrões pré-estabelecidos e de simetrias. Um típico museu moderno é composto por um conjuto de salas ligadas por corredores e escadas, sem preocupação com a prédefinição de caminhos a serem seguidos pelas pessoas.

Henriqueta é uma professora do ensino fundamental que deseja visitar o museu da Ordem Brasileira de Medicina (OBM) para mostrar aos seus alunos de ciências como o corpo humano funciona e como as cirurgias eram feitas nos séculos XIX e XX. Henriqueta quer planejar uma visita pelas salas do museu, obedecento as seguintes restrições:

• a visita deve começar e terminar em uma mesma sala;
• exceto a sala de partida, nenhuma sala do museu pode ser visitada mais de uma vez;
• a visita deve incluir pelo menos duas salas;
• os corredores são unidirecionais, ou seja, as pessoas podem caminhar, em um corredor, apenas em uma direção.
• a visita deve tomar o menor tempo possível.

Um estudo preliminar, realizado pelo próprio museu, indica o tempo médio que cada visitante fica em uma sala e quanto tempo leva-se para atravessar um corredor ou uma escada. Henriqueta quer a sua ajuda para calcular o tempo total da menor visita que ela pode efetuar, obedecendo as restrições dadas.

Escreva um programa que, dados um conjunto de salas, um conjunto de corredores e escadas que ligam essas salas e o tempo necessário para percorrer cada sala e cada corredor, determine qual é o menor tempo possível para uma visita. Note que o tempo de visita da sala onde a visita se inicia deve ser contado apenas uma vez.