| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Object Pascal: кроссплатформенные технологии > Ориентированный граф |
| Автор: Alija 8.9.2009, 21:08 |
| Дан ориентированный граф, у которого каждая дуга покрашена в один из трех цветов. Требуется найти длину кратчайшего пути из 1й вершины в N-ую, если в пути не могут идти подряд две дуги одного цвета. Входные данные В первой строке записаны N и M (2<=N<=200, 0<=M<=N*N). Далее идет M строк с описанием дуг. Каждая дуга описывается тремя целыми числами X, Y, C - дуга из вершины X в вершину Y покрашена в цвет C (1<=X,Y<=N, 1<=C<=3). Между каждой парой вершин не может быть более одной дуги в одном направлении. Выходные данные Выходные данные. Выведите длину кратчайшего пути из 1й вершины в N-ую. Если пути не существует, то выведите -1. Пример Ввод Пример #1 4 4 1 2 1 2 3 2 3 4 3 2 4 1 Пример #2 3 2 1 2 1 2 3 1 Вывод Пример №1 3 Пример №2 -1 |
| Автор: THandle 19.9.2009, 02:20 |
| Alija, уже есть какие то наработки в виде кода или же Вам нужно полное решение данной задачи?(во втором случае перемещу в соответствующий раздел) |
| Автор: virtualmacar 22.9.2009, 07:36 |
| Есть же алгоритм поиска кратчайшего пути на графе.. а закодировать алгоритм по моему дело святое, лучше разберись сам, потому что когда пойдут алгоритмы такие как автоматы мура или методики шифрования ГОСТ или АЕS или ещё что , короче к этому времени стоит научиться реализовать алгоритмы, а если совсем не охота тогда есть фриланс плати денежку ) |