Data de entrega: 14/12 ate 23:59

Escreva um programa em Python que vai calcular o caminho mais rápido entre uma origem em um destino dado. O programa recebe um grafo direcionado e informação sobre a distancia e velocidade máxima na aresta, e recebe também informação sobre a velocidade real na áreas e deve calcular o cominho mais rápido (assumindo que o motorista andará na maior velocidade permitida em cada aresta) entre uma origem e um destino dados.

Os dados tem a seguinte forma:

25.0
a b 0.4
a c 0.5 50.0
b d 1.2
b z 0.2 
z f 0.3 40.0

a b 12.5
a c 4.1
b z 0
a
z

A primeira linha indica a velocidade máxima default nas ruas da cidade, neste case, se não ha indicação de velocidade máxima na rua, assume-se que seja 25k/h

As linhas seguintes são as arestas direcionadas que possuem 3 ou quatro valores. Os dois primeiros são os vértices. O terceiro valor é a distancia em quilômetros entre os vértices. Se houver um quarto valor ele é a velocidade máxima naquele trecho e naquele sentido. O fato da velocidade máxima entre a e c ser 50k/h não significa que ele seja a velocidade no sentido de c para a. Na verdade pode não haver uma aresta de c para a (ou seja esse trecho da rua é mão única).

Ao final do grafo haverá uma linha sem dados. A partir deste ponto os dados indicam as velocidades atuais nas arestas. Neste momento a velocidade possível de a para b é só 12.5 k/h. Note que nem todas as arestas terão uma linha de atualização da sua velocidade real. Note também que algumas ruas podem ter velocidade máxima de 0k/h ou seja a rua esta fechada e aquela aresta temporariamente não existe.

Finalmente haverá duas linhas com a origem (a) e o destino (z).

Calcule

• o caminho mais curto entre origem destino e
• o caminho mais rápido entre a origem e o destino (assumindo que o motorista dirigirá na maior velocidade possível em cada segmento)

Se:

• se não houver caminho possível entre a origem e o destino imprima Nao existe caminho
• para o caminho mais curto imprima o numero de kilometros (com uma casa decimal) deste caminho, e na próxima linha a sequencia de vértices, da origem ate o destino separados por um branco.
• imprima uma linha em branco
• para o caminho mais curto, imprima o tempo de transito em minutos (sem casas decimais), e na próxima linha a sequencia de vértices, da origem ate o destino separados por um branco.

Por exemplo:

3.4
a b d f g

18
a b d e g z

Que indica que o caminho mais curto tem 3.4 kilometros, e que o caminho mais rápido tera o tempo de transito de 18 minutos

Seu programa será executado como

python3 proj.py < dados.txt

Ou seja, seu programa precisa ter as linhas no final:

if __name__ == "__main__":
     funcprincipa()

que indica que o Python executará funcprincipal (use o nome que vc quiser) como a primeira chamada do programa.

Restrições

o programa nao pode usar modulos que nao estão na biblioteca padrão.