Задача про города и дороги

@Lunch · Регистрация: 19.12.2017

Author24 — интернет-сервис помощи студентам

Здравствуйте поступило такое задание не знаю как подобраться к решению к решал подскажите пожалуйста
Вам предоставляется список городов. Каждая прямая связь между двумя городами имеет свои транспортные расходы (целое число больше 0). Цель состоит в том, чтобы найти пути минимальной стоимости между парами городов. Предположим, что стоимость каждого пути (которая является суммой затрат на все прямые соединения, принадлежащие этому пути) составляет не более 200000. Название города - это строка, содержащая символы a, ..., z и не более 10 символы длинные.
2) вход s [количество тестов <= 10]
n [количество городов <= 10000]
ИМЯ [название города]
р [количество соседей города НАИМЕНОВАНИЕ]
nr cost [nr - индекс города, подключенного к NAME (индекс первого города равен 1)] [стоимость - стоимость перевозки]
r [количество путей для поиска <= 100]
ИМЯ1 ИМЯ2 [ИМЯ1 - источник, ИМЯ2 - место назначения]
[пустая строка, разделяющая тесты]
Выход стоимость [минимальная стоимость перевозки из города ИМЯ1 в город ИМЯ2 (по одному на линию)]
Пример
Входные данные:
1
4
Gdansk
2
2 1
3 3
Быдгощ
3
1 1
3 1
4 4
бежать
3
1 3
2 1
4 1
Варшава
2
2 4
3 1
2
Гданьск Варшава
Быдгощ Варшава
Выход: 3 2

@KEKCoGEN · 08.06.2019, 17:06

Lunch, гугли про графы и поиск пути

@Lunch · 08.06.2019, 17:10 **[ТС]**

Есть представление того что параметры города должны быть записаны в классе а обьекты этого класса лежать в коллекции ArrayList только вот где записать расстояния городов друг от друга чтобы высчитать минимальный путь, ведь городов много и от одного 4(условно) дороги к другим и где мне это поместить?

@xoraxax · 08.06.2019, 18:59

про графы погуглил?

@Lunch · 08.06.2019, 19:02 **[ТС]**

да впринципе многое понял даже код нашёл сейчас осталась только проблема с обходом графа

Добавлено через 1 минуту

Java

public class Graph {
 
    //максимальное количество вершин в графе
    private final int VERTEX_MAX = 100;
    //массив для хранения вершин
    private Urbans[] urbansList;
    //текущее количество вершин в графе
    private int vertexCount;
 
    public int[][] getMatrix() {
        return matrix;
    }
 
    //матрица смежности
    private int[][] matrix;
 
 
 
    public Graph()
    {
        matrix = new int[VERTEX_MAX][VERTEX_MAX];
        //перед началом работы заполняем матрицу смежности нулями
        for(int i = 0; i < VERTEX_MAX; i++)
            for(int j = 0; j < VERTEX_MAX; j++)
                matrix[i][j] = 0;
        vertexCount = 0;
        urbansList = new Urbans[VERTEX_MAX];
    }
    public void addUrban(String label)
    {
        urbansList[vertexCount++] = new Urbans(label);
    }
 
    //добавление Urbans
    void addEdge(int begin, int end)
    {
        matrix[begin][end] = 1;
        matrix[end][begin] = 0;
    }
 
    int getSuccessor(int u)
    {
        for(int j = 0; j < vertexCount; j++)
            if(matrix[u][j] == 1 && urbansList[j].get_isVisited() == false)
                return j; //возвращает первую найденную вершину
        return -1; //таких вершин нет
    }
 
}
 
[size="1"][color="grey"][I]Добавлено через 20 секунд[/I][/color][/size]
public class Urbans {
 
    private String label;
    private boolean isVisited;
 
    public Urbans(String label)
    {
        this.label = label;
        isVisited = false;
    }
 
    public String getLabel() {
        return label;
    }
 
    public void setLabel(String label) {
        this.label = label;
    }
 
    public boolean get_isVisited() {
        return isVisited;
    }
 
    public void setVisited(boolean isVisited) {
        this.isVisited = isVisited;
    }
}

@Goongala · 08.06.2019, 20:08

Lunch,

@Lunch · 08.06.2019, 22:34 **[ТС]**

Java

public class Graph {
 
    //максимальное количество вершин в графе
    private final int VERTEX_MAX = 100;
    //массив для хранения вершин
    private Urbans[] urbansList;
    //текущее количество вершин в графе
    private int vertexCount;
 
    public int[][] getMatrix() {
        return matrix;
    }
 
    //матрица смежности
    private int[][] matrix;
 
 
 
    public Graph()
    {
        matrix = new int[VERTEX_MAX][VERTEX_MAX];
        //перед началом работы заполняем матрицу смежности нулями
        for(int i = 0; i < VERTEX_MAX; i++)
            for(int j = 0; j < VERTEX_MAX; j++)
                matrix[i][j] = 0;
        vertexCount = 0;
        urbansList = new Urbans[VERTEX_MAX];
    }
    public void addUrban(String label)
    {
        urbansList[vertexCount++] = new Urbans(label);
    }
 
    //добавление Urbans
    void addEdge(int begin, int end)
    {
        matrix[begin][end] = 1;
        matrix[end][begin] = 0;
    }
 
    int getSuccessor(int u)
    {
        for(int j = 0; j < vertexCount; j++)
            if(matrix[u][j] == 1 && urbansList[j].get_isVisited() == false)
                return j; //возвращает первую найденную вершину
        return -1; //таких вершин нет
    }
 
}

Добавлено через 29 секунд

Java

public class Urbans {
 
    private String label;
    private boolean isVisited;
 
    public Urbans(String label)
    {
        this.label = label;
        isVisited = false;
    }
 
    public String getLabel() {
        return label;
    }
 
    public void setLabel(String label) {
        this.label = label;
    }
 
    public boolean get_isVisited() {
        return isVisited;
    }
 
    public void setVisited(boolean isVisited) {
        this.isVisited = isVisited;
    }
}

Плохо я знаком с форумами))

Добавлено через 2 часа 24 минуты
а лучше использовать обход в глубь или в ширину?

@Lunch 1 / 1 / 0 Регистрация: 19.12.2017 Сообщений: 147
		1
	Задача про города и дороги 08.06.2019, 16:58. Показов 3093. Ответов 6 Метки нет (Все метки) Здравствуйте поступило такое задание не знаю как подобраться к решению к решал подскажите пожалуйста Вам предоставляется список городов. Каждая прямая связь между двумя городами имеет свои транспортные расходы (целое число больше 0). Цель состоит в том, чтобы найти пути минимальной стоимости между парами городов. Предположим, что стоимость каждого пути (которая является суммой затрат на все прямые соединения, принадлежащие этому пути) составляет не более 200000. Название города - это строка, содержащая символы a, ..., z и не более 10 символы длинные. 2) вход s [количество тестов <= 10] n [количество городов <= 10000] ИМЯ [название города] р [количество соседей города НАИМЕНОВАНИЕ] nr cost [nr - индекс города, подключенного к NAME (индекс первого города равен 1)] [стоимость - стоимость перевозки] r [количество путей для поиска <= 100] ИМЯ1 ИМЯ2 [ИМЯ1 - источник, ИМЯ2 - место назначения] [пустая строка, разделяющая тесты] Выход стоимость [минимальная стоимость перевозки из города ИМЯ1 в город ИМЯ2 (по одному на линию)] Пример Входные данные: 1 4 Gdansk 2 2 1 3 3 Быдгощ 3 1 1 3 1 4 4 бежать 3 1 3 2 1 4 1 Варшава 2 2 4 3 1 2 Гданьск Варшава Быдгощ Варшава Выход: 3 2 0

@KEKCoGEN 2398 / 2223 / 565 Регистрация: 28.12.2010 Сообщений: 8,672
	08.06.2019, 17:06	2
	Lunch, гугли про графы и поиск пути 0

@Lunch 1 / 1 / 0 Регистрация: 19.12.2017 Сообщений: 147
	08.06.2019, 17:10 [ТС]	3
	Есть представление того что параметры города должны быть записаны в классе а обьекты этого класса лежать в коллекции ArrayList только вот где записать расстояния городов друг от друга чтобы высчитать минимальный путь, ведь городов много и от одного 4(условно) дороги к другим и где мне это поместить? 0

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	08.06.2019, 18:59	4
	про графы погуглил? 0

@Goongala 1021 / 561 / 185 Регистрация: 18.08.2013 Сообщений: 2,026 Записей в блоге: 2
	08.06.2019, 20:08	6
	Lunch, 0

	08.06.2019, 22:34