Na ilha de Java, há uma ferrovia que interliga um conjunto de províncias. Porém, devido à falta de recursos durante a implantação, todos os trajetos são de via única. Ou seja, a xistência de uma rota de Jacarta à Banten não implica na existência de uma rota de Banten à Jacarta. Na verdade, mesmo se essas duas rotas existissem, elas seriam distintas e não teriam necessariamente a mesma distância.
O propósito deste problema é ajudar os usuários da ferrovia com informações a respeito das rotas existentes. Em particular, você calculará a distância de uma certa rota, o número de iferentes rotas entre duas províncias e a menor rota entre duas províncias.
Entrada do programa: Um grafo direcionado onde um vértice representa uma província e uma aresta representa uma rota entre duas províncias. O peso da aresta representa a distância ntre as duas províncias. Uma determinada rota nunca aparecerá mais de uma vez no grafo (exemplo: "AC5, DB3, AC5") e a província de partida nunca será a província de chegada ( xemplo: "AA2").
Saída do programa: Considerando o cenário de exemplo, mostrado abaixo, o programa calculará o seguinte:
1: A distância da rota A-B-C. 2: A distância da rota A-D. 3: A distância da rota A-D-C. 4: A distância da rota A-E-B-C-D. 5: A distância da rota A-E-D. 6: O número de rotas que começam em C e terminam em C com o máximo de 3 paradas. No cenário de exemplo, há duas possíveis rotas: C-D-C (com duas paradas) e C-E-B-C (com três paradas). 7: O número de rotas que começam em A e terminam em C com exatamente 4 paradas. No cenário de exemplo, há três possíveis rotas: A-B-C-D-C, A-D-C-D-C e A-D-E-B-C. 8: A distância da rota mais curta de A à C. 9: A distância da roda mais curta de B à B. 10: O número de diferentes rotas de C à C com uma distância menor que 30. No cenário de exemplo, há 7 rotas: C-D-C, C-E-B-C, C-E-B-C-D-C, C-D-C-E-B-C, C-D-E-B-C, C-E-B-C-E-B-C e C-E-B-C-E-B-C-E-B-C.
Cenário de exemplo:
Para a entrada do teste, as províncias são nomeadas utilizando apenas uma letra do alfabeto de A a E. Uma rota entre duas províncias A e B com distância 5 é representada como "AB5".
Grafo de entrada: BC4, AD5, DC8, CD8, DE6, CE2, AE7, EB3, AB5
Saída esperada: 1: 9 2: 5 3: 13 4: 22 5: ROTA NAO EXISTE 6: 2 7: 3 8: 9 9: 9 10: 7