Aula prática · exemplo completo caso por caso

beecrowd 1148 — entendendo cada caso de entrada.

O exemplo oficial possui dois casos de teste antes do 0 0. Vamos tratar cada um como um exercício independente para não misturar arestas, consultas e respostas.

Caso 1 completoCaso 2 completoGrafo originalGrafo após custo zeroConsultas
01

Como a entrada é organizada?

1

N E: quantidade de cidades e quantidade de acordos.

2

As próximas E linhas são arestas X Y H.

3

Depois vem K: quantidade de consultas.

4

As próximas K linhas são pares origem destino.

5

Quando aparecer 0 0, a entrada terminou.

Portanto, o exemplo fornecido contém 2 casos de teste completos: o primeiro começa em 4 5 e o segundo começa em 3 3.
C1

Caso de teste 1 — entrada completa

Entrada somente do caso 1

4 5
1 2 5
2 1 10
3 4 8
4 3 7
2 3 6
5
1 2
1 3
1 4
4 3
4 1

Saída somente do caso 1

0
6
6
0
Nao e possivel entregar a carta

Interpretação linha por linha

4 5
4 cidades: 1, 2, 3 e 4. 5 acordos: leremos exatamente 5 arestas.
1 2 5
Existe 1 → 2 com tempo 5.
2 1 10
Existe 2 → 1 com tempo 10.
3 4 8
Existe 3 → 4 com tempo 8.
4 3 7
Existe 4 → 3 com tempo 7.
2 3 6
Existe 2 → 3 com tempo 6.
5
Existem 5 consultas.
1 2
Consulta 1: menor tempo de 1 até 2.
1 3
Consulta 2: menor tempo de 1 até 3.
1 4
Consulta 3: menor tempo de 1 até 4.
4 3
Consulta 4: menor tempo de 4 até 3.
4 1
Consulta 5: menor tempo de 4 até 1.
02

Caso 1 — do grafo original ao grafo usado

Antes da regra especial

1 → 2 = 5
2 → 1 = 10

2 → 3 = 6

3 → 4 = 8
4 → 3 = 7

Depois da regra especial

1 → 2 = 0
2 → 1 = 0

2 → 3 = 6

3 → 4 = 0
4 → 3 = 0
Como 1→2 e 2→1 existem, esse par vira custo zero. Como 3→4 e 4→3 existem, esse par também vira custo zero. O acordo 2→3 continua custando 6 porque não existe 3→2.
0 0 6 somente 2 → 3 0 0 1 2 3 4
1234
100∞∞
2006∞
3∞∞00
4∞∞00
03

Caso 1 — resolvendo todas as 5 consultas

Consulta 1
1 → 2
0

O par 1 e 2 possui comunicação instantânea após a regra especial.

Saída: 0
Consulta 2
1 → 2 → 3
0 + 6 = 6

Chegamos em 2 sem custo e depois seguimos pela aresta 2→3 de custo 6.

Saída: 6
Consulta 3
1 → 2 → 3 → 4
0 + 6 + 0 = 6

Depois de chegar em 3, a comunicação 3→4 custa zero.

Saída: 6
Consulta 4
4 → 3
0

O par 3 e 4 também foi transformado em comunicação instantânea.

Saída: 0
Consulta 5
4 → 3 ✕ 2 → 1
não existe 3 → 2

4 chega em 3, mas a aresta entre 2 e 3 existe apenas no sentido 2→3. Portanto não conseguimos voltar para 2 e depois para 1.

Saída: Nao e possivel entregar a carta
C2

Caso de teste 2 — entrada completa

Entrada somente do caso 2

3 3
1 2 10
2 3 1
3 2 1
3
1 3
3 1
3 2

Saída somente do caso 2

10
Nao e possivel entregar a carta
0

Interpretação linha por linha

3 3
3 cidades e 3 acordos.
1 2 10
Existe 1 → 2 com tempo 10.
2 3 1
Existe 2 → 3 com tempo 1.
3 2 1
Existe 3 → 2 com tempo 1.
3
Existem 3 consultas.
1 3
Consulta 1: menor tempo de 1 até 3.
3 1
Consulta 2: menor tempo de 3 até 1.
3 2
Consulta 3: menor tempo de 3 até 2.
04

Caso 2 — montando o grafo completo

Antes da regra

1 → 2 = 10

2 → 3 = 1
3 → 2 = 1

Depois da regra

1 → 2 = 10

2 → 3 = 0
3 → 2 = 0
Somente o par 2 e 3 possui acordo nos dois sentidos. Por isso apenas 2↔3 vira custo zero. Não existe 2→1, então 1→2 continua custando 10.
10 somente 1 → 2 0 0 1 2 3
123
1010∞
2∞00
3∞00
05

Caso 2 — resolvendo todas as 3 consultas

Consulta 1
1 → 2 → 3
10 + 0 = 10

1→2 ainda custa 10. Depois 2→3 custa zero.

Saída: 10
Consulta 2
3 → 2 ✕ 1
não existe 2 → 1

3 chega em 2 por custo zero, mas não existe uma aresta de 2 para 1.

Saída: Nao e possivel entregar a carta
Consulta 3
3 → 2
0

2 e 3 possuem acordos recíprocos, então o envio é instantâneo.

Saída: 0
06

Agora fica claro onde o Dijkstra entra

Nos exemplos pequenos conseguimos enxergar os caminhos. O programa precisa fazer a mesma coisa automaticamente.

1

Monte o grafo lendo as E linhas.

2

Aplique a regra de custo zero quando existir ligação direta nos dois sentidos.

3

Para cada consulta, inicialize dist[origem] = 0 e as demais como infinito.

4

Escolha sempre o vértice não visitado com a menor distância acumulada.

5

Relaxe as arestas: tente melhorar o custo dos vizinhos.

6

Se o destino continuar infinito, imprima Nao e possivel entregar a carta.

Exemplo de Dijkstra: Caso 1, consulta 1 → 4

PassoEscolhidodist[1]dist[2]dist[3]dist[4]Atualização
Inicial—0∞∞∞Origem = 0
1100∞∞1→2 custa 0
22006∞0 + 6 = 6
3300666 + 0 = 6
440066Resposta = 6
07

Código completo e comentado em Python 3.11

# Um custo muito alto representa uma ligação inexistente.
INF = 10 ** 15


def dijkstra(origem, destino, n):

    # dist guarda o menor custo conhecido desde a origem.
    # visitado indica as cidades cujo menor custo já foi confirmado.
    dist = [INF] * (n + 1)
    visitado = [False] * (n + 1)

    dist[origem] = 0

    for _ in range(n):

        menor = INF
        atual = -1

        # Escolhe o não visitado com menor distância.
        for cidade in range(1, n + 1):
            if not visitado[cidade] and dist[cidade] < menor:
                menor = dist[cidade]
                atual = cidade

        # Nenhuma outra cidade alcançável restou.
        if atual == -1:
            break

        visitado[atual] = True

        # Ao confirmar o destino, sua distância já é mínima.
        if atual == destino:
            break

        # Relaxamento.
        for vizinho in range(1, n + 1):

            peso = grafo[atual][vizinho]

            if peso != INF:

                novo_custo = dist[atual] + peso

                # Uma rota mais barata substitui a estimativa anterior.
                if novo_custo < dist[vizinho]:
                    dist[vizinho] = novo_custo

    return dist[destino]


while True:

    # Cada caso começa pela quantidade de cidades e acordos.
    n, e = map(int, input().split())

    # O par 0 0 encerra toda a entrada.
    if n == 0 and e == 0:
        break

    # A matriz guarda o custo direto; INF significa ausência de acordo.
    grafo = [
        [INF] * (n + 1)
        for _ in range(n + 1)
    ]

    for cidade in range(1, n + 1):
        grafo[cidade][cidade] = 0

    for _ in range(e):

        x, y, h = map(int, input().split())

        # Em entradas repetidas, preservamos o menor custo direto.
        grafo[x][y] = min(grafo[x][y], h)

        # Se o acordo inverso já existe, os dois custos viram zero.
        if grafo[y][x] != INF:
            grafo[x][y] = 0
            grafo[y][x] = 0

    # Cada consulta executa Dijkstra entre uma origem e um destino.
    k = int(input())

    for _ in range(k):

        origem, destino = map(int, input().split())

        resposta = dijkstra(origem, destino, n)

        # INF ao final significa que nenhuma rota alcançou o destino.
        if resposta == INF:
            print("Nao e possivel entregar a carta")
        else:
            print(resposta)

    # O formato exige uma linha vazia depois de cada caso.
    print()
Ordem mental para resolver o 1148: ler um caso → montar seu grafo → ajustar reciprocidades → responder suas K consultas → imprimir linha vazia → ler o próximo caso.
✓

Entrada oficial completa, agora separada mentalmente

CASO 1
4 5
1 2 5
2 1 10
3 4 8
4 3 7
2 3 6
5
1 2
1 3
1 4
4 3
4 1

CASO 2
3 3
1 2 10
2 3 1
3 2 1
3
1 3
3 1
3 2

FIM
0 0
Os textos “CASO 1”, “CASO 2” e “FIM” acima são apenas marcações didáticas. Eles não fazem parte da entrada enviada ao beecrowd.