Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
10278 – Fire Station

El problema es de Grafos y se resuelve utilizando Dijkstra.
Lo que nos dan en la entrada es la descripción de unas intersecciones de alguna ciudad, en la cual ya existen algunas estaciones de bombero, y lo que nos piden es decidir en que lugar hay que colocar la nueva estación para minimizar la máxima distancia desde una estación hacia todas las intersecciones.
Esto se resume a un Dijkstra con múltiples fuentes. Lo que hay que hacer es colocar la nueva en la estación 0, luego en la 1, luego la 2, etc, e ir determinando cual de todas las estaciones es la mejor para colocar la nueva estación de bomberos.

Ejemplo:

1 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10

Ya se dispone de una estación de bomberos en la intersección 2.
Ahora al agregar la estación nueva en la 1 tenemos que la distancia mas grande hacia las demás es 20
Si fuera en la 2 seria 30
Si fuera en la 3 seria 20
Si fuera en la 4 seria 20
Si fuera en la 5 seria 10
Y si fuera en la 6 seria 20

Por lo tanto la respuesta es 5.

Código en C++

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: