|
Java форум JavaTalks
форум программистов
|
|
|
|
| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
dim8806 : 2
Новичок
|
 Янв 29, 2012 8:37 |
 |
|
люди добрые помоги с задачкой:
Есть города А, B, C, D, E, F, G.
В таблице указаны цены на билеты из (горизонтальная ось) в (вертикальная ось).
Если из города в этот же город - то не нужно - цена 0;
Если такого рейса нет - то значение -1.
- найти самый дешевый путь из точки А в точку В.
0 10 5 3 20 7 100
10 0 7 10 20 7 -1
20 10 0 250 10 7 5
10 20 6 0 8 10 2
3 150 -1 6 0 7 2
8 200 5 50 40 0 20
120 7 -1 -1 -1 50 0
Знаю, что нужно решать через алгоритм Дейкстры, но с матрицей совсем не получается  Спасибо! |
|
|
|
 |
Vantuz-Subhuman : 660
Постоянный посетитель
Откуда: издиснейленда
|
| Янв 29, 2012 9:46 |
| |
|
| dim8806 писал(а): |
люди добрые помоги с задачкой:
Есть города А, B, C, D, E, F, G.
В таблице указаны цены на билеты из (горизонтальная ось) в (вертикальная ось).
Если из города в этот же город - то не нужно - цена 0;
Если такого рейса нет - то значение -1.
- найти самый дешевый путь из точки А в точку В.
0 10 5 3 20 7 100
10 0 7 10 20 7 -1
20 10 0 250 10 7 5
10 20 6 0 8 10 2
3 150 -1 6 0 7 2
8 200 5 50 40 0 20
120 7 -1 -1 -1 50 0
Знаю, что нужно решать через алгоритм Дейкстры, но с матрицей совсем не получается Спасибо! |
Странная у вас таблица. Почему из города 2 в город 0 проезд стоит 5 рублей, а из города 0 в город 2 - 20 рублей?
Матрица подобного рода должна быть зеркальной относительно главной диагонали. Посмотрите, например, на такую таблицу:
Или рассчитывать разную цену в разных направлениях это часть задачи?
_________________
«One should never underestimate the predictability of stupidity»,
«Never attribute to malice that which can be adequately explained by stupidity» |
|
|
|
|
dim8806 : 2
Новичок
|
| Янв 29, 2012 10:36 |
| |
|
| К сожалению, что имеем то имеем, таблица странная |
|
|
|
|
Vantuz-Subhuman : 660
Постоянный посетитель
Откуда: издиснейленда
|
| Янв 29, 2012 11:14 |
| |
|
Попробуйте так:
| Код: |
import java.util.LinkedList;
import java.util.Queue;
public class Test {
public static void main(String args[]) {
int[][] arr = {
{ 0, 10, 5, 3, 20, 7, 100 },
{ 10, 0, 7, 10, 20, 7, -1 },
{ 20, 10, 0, 250, 10, 7, 5 },
{ 10, 20, 6, 0, 8, 10, 2 },
{ 3, 150, -1, 6, 0, 7, 2 },
{ 8, 200, 5, 50, 40, 0, 20 },
{ 120, 7, -1, -1, -1, 50, 0 },
};
System.out.println(findPrice(arr, 2, 4));
}
public static int findPrice(int[][] prices, final int A, final int B)
throws ArrayIndexOutOfBoundsException {
if (A == B)
return 0;
if (prices[B][A] > 0)
return prices[B][A];
Queue<RoadSegment> segmentsq = new LinkedList<RoadSegment>();
segmentsq.offer(new RoadSegment(A, 0));
RoadSegment shortest = null;
RoadSegment seg;
int p;
while (!segmentsq.isEmpty()) {
seg = segmentsq.poll();
if ((p = prices[B][seg.town]) > 0) {
seg.price += p;
if (shortest == null || seg.price < shortest.price) {
shortest = seg;
}
} else {
for (int b = 0; b < prices.length; b++) {
if ((p = prices[b][seg.town]) > 0) {
segmentsq.offer(new RoadSegment(b, seg.price + p));
}
}
}
}
return shortest.price;
}
private static class RoadSegment {
private int town;
private int price;
public RoadSegment(int town, int price) {
this.town = town;
this.price = price;
}
}
} |
Для тестирования были найдены пути:
из 6 в 1 --> 6-3=2 + 3-1=10 :: 12
из 2 в 4 --> 2-0=5 + 0-4=3 :: 8
Прямая дорога воспринимается, как самый короткий и дешёвый путь (если что, можно изменить)
_________________
«One should never underestimate the predictability of stupidity»,
«Never attribute to malice that which can be adequately explained by stupidity» |
|
|
|
|
Vantuz-Subhuman : 660
Постоянный посетитель
Откуда: издиснейленда
|
| Янв 29, 2012 13:34 |
| |
|
Только надо допилить запоминание уже пройденных городов, а то я забыл и есть шанс упасть в бесконечный цикл.
UPD: Вот так вроде работает:
| Код: |
import java.util.LinkedList;
import java.util.Queue;
public class Test {
public static void main(String args[]) {
int[][] arr = {
{ 0, 10, 5, 3, 20, 7, 100 },
{ 10, 0, 7, 10, 20, 7, -1 },
{ 20, 10, 0, 250, 10, 7, 5 },
{ 10, 20, 6, 0, 8, 10, 2 },
{ 3, 150, -1, 6, 0, 7, 2 },
{ 8, 200, 5, 50, 40, 0, 20 },
{ 120, 7, -1, -1, -1, 50, 0 },
};
System.out.println(findPrice(arr, 2, 4));
}
public static int findPrice(int[][] prices, final int A, final int B)
throws ArrayIndexOutOfBoundsException {
if (A == B)
return 0;
if (prices[B][A] > 0)
return prices[B][A];
Queue<Town> segmentsq = new LinkedList<Town>();
segmentsq.offer(new Town(null, A, 0));
Town shortest = null;
Town town;
int p;
while (!segmentsq.isEmpty()) {
town = segmentsq.poll();
if ((p = prices[B][town.town]) > 0) {
Town t = new Town(town, B, p);
if (shortest == null || t.getTotalPrice() < shortest.price) {
shortest = t;
}
} else {
for (int b = 0; b < prices.length; b++) {
if ((p = prices[b][town.town]) > 0 && !town.isGoesThru(b)) {
segmentsq.offer(new Town(town, b, p));
}
}
}
}
return shortest.getTotalPrice();
}
private static class Town {
private Town prevTown;
private int town;
private int price;
public Town(Town prevTown, int town, int price) {
if (prevTown != null && prevTown.isGoesThru(town))
throw new IllegalArgumentException();
this.prevTown = prevTown;
this.town = town;
this.price = price;
}
public boolean isGoesThru(int town) {
if (this.town == town)
return true;
if (prevTown == null)
return false;
return prevTown.isGoesThru(town);
}
public int getTotalPrice() {
int price = this.price;
if (prevTown != null) {
price += prevTown.getTotalPrice();
}
return price;
}
}
} |
Маршрут из 2 в 4:
2 -> 0 = 5 + 0 -> 4 = 3 ->> 8
Если заменить значение 0х4 с 3 на -1, то выбирается маршрут:
2 -> 3 = 6 + 3 -> 4 = 6 ->> 12
_________________
«One should never underestimate the predictability of stupidity»,
«Never attribute to malice that which can be adequately explained by stupidity» |
|
|
|
|
Skipy : 4805
Я тут живу!
Откуда: Москва, Россия
|
| Янв 30, 2012 11:24 |
| |
|
| Vantuz-Subhuman писал(а): |
Странная у вас таблица. Почему из города 2 в город 0 проезд стоит 5 рублей, а из города 0 в город 2 - 20 рублей?
|
Просто не метрическая система.  Почему из Москвы в Токио лететь 9 часов, а обратно 10?
_________________
С уважением,
Евгений aka Skipy
www.skipy.ru
P.S. Я НЕ решаю задачи ЗА других! |
|
|
|
|
|
|
Страница 1 из 1
|
Список форумов
-> Основы языка Java |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
|
|
