Camino máximo P13664


Statement
 

pdf   zip

html

Un país tiene n ciudades conectadas por carreteras bidireccionales. Se sabe que, para cada par de ciudades x e y, existe exactamente una manera de ir de x a y sin pasar más de una vez por la misma ciudad. Cada carretera tiene una cierta longitud. Calculad el camino de longitud máxima que no repite ninguna ciudad.

Entrada

Una entrada consiste en como mucho 10 casos. Cada caso comienza con el número de ciudades n ≤ 105, seguido de n − 1 líneas con información de cada carretera: las dos ciudades conectadas directamente y la longitud de la carretera, que está siempre entre 1 y 1000. Las ciudades se numeran de 1 a n. Ninguna entrada será mayor de 2 Mb.

Salida

Para cada caso, escribid en una línea la longitud del camino más largo. Vuestro programa dispone de un segundo de CPU para resolver todos los casos de una entrada.

Puntuación

  • TestA:  20 Puntos 

    Casos con 1 ≤ n ≤ 3

  • TestB:  30 Puntos 

    Casos con 1 ≤ n ≤ 100

  • TestC:  20 Puntos 

    Casos con 1 ≤ n ≤ 105 y donde no existen caminos de más de 1000 pasos.

  • TestD:  30 Puntos 

    Casos con 1 ≤ n ≤ 105.

Public test cases

  • Input

    2
1 2 100

1

3
1 3 10
2 3 5

4
1 2 10
1 3 20
1 4 40

    Output

    100
0
15
60
    • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++