Comunidad PHPeros
Otros => Los Retos PHPeros => Mensaje iniciado por: good en 26 de Agosto de 2011, 13:00:04 pm
-
Hola, propongo hacer un programa que reciba un grafo (el formato de la entrada está abajo) y que devuelva la mínima distáncia del nodo 0 a cualquier otro nodo.
el grafo será dirigido
un ejemplo de grafo dirigido es éste:
(https://chart.googleapis.com/chart?cht=gv:neato&chl=digraph{0-%3E1,0-%3E2,0-%3E3,1-%3E3,2-%3E1,3-%3E4}&chs=400x400)
El nodo de origen es el nodo 0, y el programa devovlerá la distáncia mínima desde el nodo 0 al nodo n
En este grafo salen las distáncias mínimas desde el nodo 0 a cualquier nodo:
(http://img854.imageshack.us/img854/5273/sinttulocy.png)
(si no se entiende del todo bien responded xD)
El programa recibirá la descripción de un grafo siguiendo el siguiente formato:
un número N que es el total de nodos (empezando desde el 0)
a continuación, N lineas que describan las conexiones de cada nodo, que será un número Ni que indicará el nodo que vamos a definir, un número Si con el total de conexiones, seguido de Si números (los nodos con los que conecta)
Al final un número del 0 al N-1 que indique el nodo del que sacaremos la distáncia mínima
Ejemplo de entrada (el de la imagen):
5
0 3 1 2 3
1 1 3
2 1 1
3 1 4
4 0
4
Ejemplo de salida (el de la imagen):
2
hemos computado la distáncia mínima del nodo 0 al nodo 4, que es 2