Download Speed.

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Rust, Scala, ~~Swift~~, VB, Zig

Consideremos una red formada por $n$ ~n~ ordenadores y $m$ ~m~ conexiones. Cada conexión especifica la velocidad a la que un ordenador puede enviar datos a otro. Kotivalo quiere descargar unos datos de un servidor.

¿Cuál es la velocidad máxima a la que puede hacerlo utilizando las conexiones de la red?

Entrada

La primera línea de entrada tiene dos números enteros $n$ ~n~ y $m$ ~m~: el número de ordenadores y de conexiones. Los ordenadores se numeran $1,2,m,n$ ~1,2,m,n~. El ordenador $1$ ~1~ es el servidor y el ordenador $n$ ~n~ es el ordenador de Kotivalo. A continuación, hay $m$ ~m~ líneas que describen las conexiones. Cada línea tiene tres enteros $a, b$ ~a, b~ y $c$ ~c~: el ordenador $a$ ~a~ puede enviar datos al ordenador $b$ ~b~ a la velocidad $c$ ~c~.

Salida

Imprime un entero: la velocidad máxima a la que Kotivalo puede descargar datos.

Restricciones

$1 \leq n \leq 500$ ~1 \leq n \leq 500~
$1 \leq m \leq 1000$ ~1 \leq m \leq 1000~
$1 \leq a,b \leq n$ ~1 \leq a,b \leq n~
$1 \leq c \leq 10^9$ ~1 \leq c \leq 10^9~

Ejemplo de Entrada

Ejemplo de Salida

Comments

1

El_Yoryo commented on July 18, 2025, 1:34 p.m.

Buena eitorial aqui :

=====> Maximum Flow <========

1

Luisito0101 commented on July 17, 2025, 1:08 p.m.

Quisiera saber a qué se refieren con "velocidad" en este problema

1

juan_alejandro commented on May 6, 2025, 5:33 p.m.

¿Porque la respuesta es 6 no debería ser 4.5 al ser la mejor velocidad ir del 1 al 3 con v=4 y luego de de 3 a 4 con v=5 y así llegaría con una v=(4+5)/2 que sería v=4.5?