+

Это задача для саморазвития, и представляет больше теоретический интерес, чем практический :).
Попробуйте для себя решить задачи Single-Source Shortest Path и All-Pairs Shortest Path для взвешенных ориентированных графов без рёбер отрицательного веса, с помощью MapReduce. Также оцените сложность работы — в зависимости от V (количества вершин), E (количества рёбер), k (количества нод, на которых происходит запуск MapReduce).

Аналогично.

А в ШАД ты учился/учишься? Не увидел тебя в списках ШАДовцев (возможно, просто плохо искал) 2011-2013 года и 2012-2014 года.
По поводу списков — делается с использованием двоичной кучи, кажется за O(n*log(m)), где n — общее количество элементов, m — количество списков.
А я не подавал на стажировку (нет желания бросать работу, меняя её на стажировку).
Это был вопрос к lex.pl)). dou сбил форматирование).