adalbertorsilva / TWTrains

Problema: Os serviços suburbanos locais da estrada de ferro de um número de cidades em Kiwiland. Por causa de questões monetárias, todas as faixas são 'one-way'. Ou seja, uma rota de Kaitaia para Invercargill não implica a existência de uma rota de Invercargill para Kaitaia. Na verdade, mesmo que ambas as rotas de fazer acontecer de existir, eles são distintos e não são necessariamente a mesma distância! O objetivo deste problema é ajudar a ferrovia fornecer aos seus clientes informações sobre as rotas. Em particular, você vai calcular a distância ao longo de uma determinada rota, o número de rotas diferentes entre duas cidades, eo caminho mais curto entre duas cidades. Entrada: Um grafo dirigido onde um nó representa uma cidade e uma borda representa uma rota entre duas cidades. A ponderação da borda representa a distância entre as duas cidades. A rota determinada nunca vai aparecer mais de uma vez, e para uma determinada rota, a cidade de início e fim não será a mesma cidade. Saída: Para entrada de teste de 1 a 5, se não existir essa rota, a saída de 'NO tal rota ". Caso contrário, siga a rota como dado, não fazer quaisquer paradas extras! Por exemplo, o primeiro problema que significa a começar na cidade A, então viajar directamente para cidade B (uma distância de 5), em seguida, directamente para a cidade C (a uma distância de 4). 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 viagens a partir de C e terminando em C com um máximo de 3 pontos. Nos dados de exemplo abaixo, existem duas dessas viagens: CDC (2 paragens). e C-E-B-C (3 pontos). 7. O número de viagens a partir de A e terminando em C com exatamente quatro paradas. Nos dados de exemplo abaixo, há três tais viagens: A a C (via B, C, D); A a C (via D, C, D), e A a C (via D, E, B). 8. O comprimento do caminho mais curto (em termos de distância a percorrer) de A a C. 9. O comprimento do caminho mais curto (em termos de distância a percorrer) de B para B. 10. O número de vias diferentes de C a C, a uma distância de menos de 30. Nos dados da amostra, as viagens são: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC. Entrada de teste: Para a entrada de ensaio, as cidades são nomeados usando as primeiras letras do alfabeto de A a E. A rota entre duas cidades (A e B a) com uma distância de 5 é representada como AB5. Gráfico: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, ae7 Saída esperada: Saída # 1: 9 Saída # 2: 5 Saída # 3: 13 Saída # 4: 22 Saída # 5: NÃO tal rota Saída # 6: 2 Saída # 7: 3 Saída # 8: 9 Saída # 9: 9 Saída # 10: 7