Aqui tienes la implementación de Dijkstra (era realmente sencilla de buscar en google
...):
http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra
Ahora solo has de leer la entrada según tus requerimientos y con esos valores llamar al algoritmo.
Eso ya lo dejo en tus manos :)