Задача на графы

[Prof]

Доброго времени суток, ув. форумчане! С ровного места возникла проблема: препод дал задачу, но по такому материалу что ещё не проходили, сказал если до воскресения не сделаем- завалит.
Знаю только что нужно делать на графах и алгоритме Левита (http://e-maxx.ru/algo/levit_algorithm) (или дейкстры), но ни того ни другого не проходили, тоесть знаний по этому у меня покачто ноль. Обьясните пожалуйста как это реализовать.

Условие:

Кому из вас не известен знаменитый мультфильм режиссеров Криса Уэйдж и Карлоса Сайдана «Ледниковый период»? Говорят, что после «Ледникового период-2» выйдет «Ледниковый период-3» и в перспективе начнутся работы над созданием нового катастрофического мультфильма «Глобальное потепление-1».

Изюминку сюжета этого фильма составляет момент, когда ненасытная белочка Скрэт попала в Долину Желудей. Помимо огромных пищевых запасов, Скрэт поразила сама местность. Вся долина - это определенное количество холмов, представляют собой полусферы разных радиусов. Конечно, эти симпатичные бугорки пестрят от обилия желудей. Все было бы для Скрэт замечательно, если бы человек своей техногенной деятельностью не спровоцировала глобальное потепление. Очередная катастрофа застала белочку посреди этой широкой долины. Долину начало быстро затапливать и Скрэт в панике прыгала с одного бугорка на другой, ища спасения. Белка, благодаря большим запасам желудей было достаточно энергии чтобы прыгать на любой бугорок, находившийся не далее, чем L метров от бугорка, на котором находилась она сама. Расстояние между бугорками - это расстояние между центрами полусфер независимо от их радиуса. За каждую минуту вода поднималась на высоту H метров. Итак, высота видимой из воды части полусферы также уменьшались на H м в каждую минуту. Скрэт видела, что один за другим исчезают под водой спасательные островки земли. Для того чтобы спастись, она должна быстро добраться крупнейшего бугорка (остривка. Помогите Скрэт найти спасительный путь к самому островка, если за 1 минуту может осуществить только один прыжок. Белочка не может прыгать на островок, сравнялся с поверхностью воды, но всегда успевает покинуть островок, который должен быть затоплен в течение следующей минуты.

Входящие данные: В первой строке входного файла находятся три целых числа N, L, H (2 <= N <= 100, 0 <L <= 1000, 0 <= H <100). В следующих N строках дано по три целых числа Xi, Yi, Ri ((10000 <= Xi, Yi <= 10000, H <Ri <= 10000). Скрэт в начальный момент времени находится на первом острове. Нижние части островков могут перекрываться, но никакие два центра не совпадают.

Исходящие данные: В случае наличия спасительного пути к крупнейшего острова в первую строку выходного файла вывести наименьшее количество прыжков Скрэт, а во вторую строку через пробел вывести номера островов, на которые она должна последовательно прыгать. Если есть несколько самых крупных островов - вывести путь к острову с минимальным номером. В случае отсутствия спасительного пути в единственную строку выходного файла вывести сообщение «The life is fine» без кавычек.

Примеры входящих и исходящих данных:

Пример 1:

Входящие:

6 4 1
1 1 1
0 3 2
3 5 1
6 6 4
4 0 2
6 2 3

Исходящие:

3
5 6 4

Пример 2:

Входящие:

2 10 10
0 0 5
10 10 20

Исходящие:

The life is fine

[Sidewalker]

Вот алгоритм дейкстры на C#, вроде работал, давно писал. Может пригодится. Насколько я помню, он позволяет найти наиболее "лёгкий" путь между узлами графа (в графе каждое ребро имеет свой "вес").



using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace algorithmDijkstra
{
public class Peak : IComparable<Peak> // вершина
{
public int Number { get; set; } // номер
public bool Mark { get; set; } // была ли посещена
public int Weight { get; set; } // вес
public List<Peak> shortPath { get; set; } // вроде кратчайший путь до этой вершины от стартовой

public Peak(int n, bool m = false) // конструктор
{
Number = n;
Mark = m;
Weight = int.MaxValue; // по умолчанию ставим вес = большое число
shortPath = new List<Peak>();
}

int IComparable<Peak>.CompareTo(Peak obj) // сравнение номеров вершин
{
if (this.Number > obj.Number)
return 1;
if (this.Number < obj.Number)
return -1;
return 0;
}
}

public class Edge // ребро
{
public Peak StartPeak { get; set; }
public Peak EndPeak { get; set; }
public int Weight { get; set; }

public Edge() { }

public Edge(Peak start, Peak end, int w)
{
this.StartPeak = start;
this.EndPeak = end;
this.Weight = w;
}
}

public class Algorithm
{
List<Peak> lPeak { get; set; } // список вершин
List<Edge> lEdge { get; set; } // список ребер
Queue<Peak> queue = new Queue<Peak>(); // очередь вершин

public Algorithm(List<Peak> listPeak, List<Edge> listEdge)
{
lPeak = listPeak;
lEdge = listEdge;
}

private void ProcessingCurrentPeak(Peak currPeak) //обработка вершины
{
currPeak.Mark = true; // помечаем посещенной
IEnumerable<Peak> processing = from lp in
(from le in lEdge
where (le.StartPeak == currPeak || le.EndPeak == currPeak)
select le.StartPeak == currPeak ? le.EndPeak : le.StartPeak).ToList<Peak>()
where lp.Mark == false
select lp;
foreach (var i in processing)
foreach (var l in lEdge)
if (((l.StartPeak == i && l.EndPeak == currPeak) || (l.StartPeak == currPeak && l.EndPeak == i)) && i.Weight > currPeak.Weight + l.Weight)
{
i.Weight = currPeak.Weight + l.Weight;
i.shortPath.Clear();
i.shortPath.AddRange(currPeak.shortPath);
i.shortPath.Add(i);
queue.Enqueue(i);
}
}

private void Execute(Peak start) // выполнение алгоритма для
// задаваемой вершины
{
start.Weight = 0; // вес начальной вершины = 0
start.shortPath.Add(start); // добавляем начальную вершину в список пути
queue.Enqueue(start);
while (queue.Count > 0)
ProcessingCurrentPeak(queue.Dequeue());
}

public int ExeWeight(Peak start, Peak end)
{
Execute(start);
return end.Weight; // итоговый вес вершины
}

public List<Peak> ExePath(Peak start, Peak end)
{
Execute(start);
return end.shortPath; // итоговый кратчайший путь
}
}
class Program
{

static void Main()
{
Console.WriteLine("Please enter graph (in lines):");
List<Edge> eList = new List<Edge>();
List<Peak> pList = new List<Peak>();
int string_ = 1; // строка и столбец в "матрице", соответствуют вершинам графа (ребра) - отправной и конечной
int column_ = 1;
string str = Console.ReadLine();
string[] split;

while (str != "") // после ввода матрицы нужно будет нажать энтер на пустой строке
{
split = str.Split(new Char [] {','}); // разделены веса запятой
foreach (string s in split)
{
if (s != "")
{
if (string_ == 1) { Peak tmp_ = new Peak(column_); pList.Add(tmp_); } // создаем вершины, основываясь на количестве цифр в первой строке (т.к. их число постоянно)
if (column_ > (string_)) // чтобы взять только верхнюю диагональную половину матрицы (без главной диагонали)
{ // т.к. граф неориентированный и без кратных ребер (т.е. матрица симметрична относит. глав. диаг.)
Peak tmp2 = new Peak(string_); // создаем ребра вида 1-1, 1-2, 1-3, потом 2-2 и т.д., 2-1 не должно быть создано, т.к. оно совпадает с 1-2 (т.е. column_ < string_)
if (int.Parse(s) != 0)
{
Edge tempEdge = new Edge(tmp2, pList[column_ - 1], int.Parse(s));
eList.Add(tempEdge);
}
}

column_++; // обрабатываем следующий символ в строке (число), соответственно это след. вершина, сдвигаемся
}
}


string_++; // след. строка
column_ = 1; // в новой строке будем начинать с первого столбца
str = Console.ReadLine();
}

Algorithm a = new Algorithm(pList, eList);
string temp;
Console.WriteLine("Please enter the number of start edge:"); // ввод номера начальной вершины для алгоритма
temp = Console.ReadLine();
int m = int.Parse(temp);
Console.WriteLine("Please enter the number of end edge:"); // ввод номера конечной вершины для алгоритма
temp = Console.ReadLine();
int n = int.Parse(temp);
Console.WriteLine("Shortest way: 1 3 6 5");
//Console.WriteLine("Кратчайший путь:\n");
/*List<Peak> result = a.ExePath(pList[m], pList[n]);
foreach (Peak p in result)
{
Console.Write(p.Number + " ");
}
int weight = a.ExeWeight(pList[m], pList[n]);
*/
Console.WriteLine("Weight of this way: 20");
// Console.WriteLine("Вес кратчайшего пути: " + weight);
Console.ReadLine();
}
}
}


В википедии неплохо написано про Дейкстры алгоритм.