С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.90/21: Рейтинг темы: голосов - 21, средняя оценка - 4.90
Заяц, просто Заяц.
 Аватар для Fury67
666 / 280 / 156
Регистрация: 12.11.2017
Сообщений: 882

Найти длину кратчайшего пути из А в B для взвешенного неориентированного графа

19.11.2019, 17:33. Показов 4352. Ответов 9

Студворк — интернет-сервис помощи студентам
Здравствуйте. Программа находит длину кратчайшего пути из А в B для взвешенного неориентированного графа. Формат входных данных: количество вершин; количество путей; вершина А - вершина B - вес ребра. Выдает на одном из тестов неправильный ответ. Есть идеи, на каких входных данных валится алгоритм?

Пример входных данных :
3 2
0 1 0
1 2 2
0 1

Вывод:
2


C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <vector>
#include <set>
#include <list>
 
class IGraph
{
public:
    virtual ~IGraph() {}
    virtual int size() const = 0;
    virtual void AddArc(int from, int to, int weight) = 0;
    virtual void GetArc(int vertex, std::vector<std::pair<int, int>> &vertices) const = 0;
};
 
class Graph : public IGraph {
public:
    Graph(int n);
    ~Graph() {};
 
    void AddArc(int from, int to, int weight);
    void GetArc(int vertex, std::vector<std::pair<int, int>> &vertices) const;
 
    int size() const {
        return vertexNumber;
    }
 
private:
    int vertexNumber;
    std::vector<std::list<std::pair<int, int>>> graph;
};
 
 
Graph::Graph(int size) : vertexNumber(size), graph(vertexNumber, std::list<std::pair<int, int>>()) {}
 
 
void Graph::AddArc(int from, int to, int weight)
{
    graph[from].push_back(std::make_pair(to, weight));
    graph[to].push_back(std::make_pair(from, weight));
}
 
 
void Graph::GetArc(int vertex, std::vector<std::pair<int, int>> &vertices) const
{
    vertices.clear();
    for (const std::pair<int, int> &i : graph[vertex]) {
        vertices.push_back(i);
    }
}
 
 
void build1(Graph const &graph, int from, int to) {
    std::vector<bool> used(graph.size(), false);
    std::vector<int> dlina(graph.size(), 10001);
    dlina[from] = 0;
    std::set<std::pair<int, int>> queue;
    queue.emplace(std::make_pair(0, from));
 
    while (!queue.empty()) {
        int v = (queue.begin())->second;
        queue.erase(queue.begin());
        used[v] = true;
 
        std::vector<std::pair<int, int>> a;
        graph.GetArc(v, a);
 
        for (std::pair<int, int> c : a) {
            if (dlina[c.first] > dlina[v] + c.second) {
                if (dlina[c.first] != 10001)
                    queue.erase(std::make_pair(dlina[c.first], c.first));
                dlina[c.first] = dlina[v] + c.second;
                queue.emplace(std::pair<int, int>(dlina[c.first], c.first));
            }
        }
    }
 
    if (dlina[to] != 10001) {
        std::cout << dlina[to];
    }
    else {
        std::cout << "0";
    }
}
 
 
int main() {
    int N, M, k, l, w;
    std::cin >> N >> M;
    if (N != 0 && M != 0) {
        Graph graph(N);
        for (int i = 0; i < M; i++) {
            std::cin >> k >> l >> w;
            graph.AddArc(k, l, w);
        }
        int from, to;
        std::cin >> from >> to;
 
        build1(graph, from, to);
    }
    else {
        std::cout << "0";
    }
    return 0;
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
19.11.2019, 17:33
Ответы с готовыми решениями:

Алгоритм Форда Беллмана для НЕориентированного взвешенного графа
Имеется задание - найти минимальный путь с вершины V0 в вершину V4 с помощью алгоритма Форда Беллмана. В инете все примеры для...

Ввод списка ребер для взвешенного неориентированного графа
Здравствуйте, подскажите, пожалуйста, как сделать следующую вещь. Имеется вот такой код для поиска минимального остовного дерева в...

Найти кратчайшее расстояние из вершины v1 неориентированного взвешенного графа в другие вершины графа
Пользуясь алгоритмом Дейкстры, найти кратчайшее расстояние из вершины v1 неориентированного взвешенного графа в другие вершины графа....

9
 Аватар для FFPowerMan
2156 / 1236 / 508
Регистрация: 11.10.2018
Сообщений: 6,240
19.11.2019, 17:44
Так а вершины с 0 что-ли начинаются?
0
Just Do It!
 Аватар для XLAT
4201 / 2657 / 654
Регистрация: 23.09.2014
Сообщений: 8,958
Записей в блоге: 3
19.11.2019, 17:44
ссылку на проверяльщик дать можете?
0
 Аватар для FFPowerMan
2156 / 1236 / 508
Регистрация: 11.10.2018
Сообщений: 6,240
19.11.2019, 17:45
Цитата Сообщение от Fury67 Посмотреть сообщение
Пример входных данных :
3 2
0 1 0
1 2 2
0 1
- и зачем здесь последняя строчка?
0
Заяц, просто Заяц.
 Аватар для Fury67
666 / 280 / 156
Регистрация: 12.11.2017
Сообщений: 882
19.11.2019, 17:48  [ТС]
Цитата Сообщение от FFPowerMan Посмотреть сообщение
- и зачем здесь последняя строчка?
Вершина А, вершина B. То есть путь из А в В.

Добавлено через 1 минуту
Цитата Сообщение от FFPowerMan Посмотреть сообщение
Так а вершины с 0 что-ли начинаются?
Да.
0
Just Do It!
 Аватар для XLAT
4201 / 2657 / 654
Регистрация: 23.09.2014
Сообщений: 8,958
Записей в блоге: 3
19.11.2019, 18:35
Fury67,
Правильно ли я интерпретирую входные данные?
Code
1
2
3
4
5
6
7
Пример входных данных :
3 2    // 3 вершины, 2 ребра
0 1 0  // из 0 в 1 длина 0
1 2 2  // из 1 в 2 длина 2
0 1    // 0 это A, 1 это B
Вывод:
2
скорее нет,
иначе каким боком вывод 2 ???
если должен быть 0.
0
Заяц, просто Заяц.
 Аватар для Fury67
666 / 280 / 156
Регистрация: 12.11.2017
Сообщений: 882
19.11.2019, 18:42  [ТС]
XLAT, да, вывод ноль. Ошибся при наборе здесь.
0
Just Do It!
 Аватар для XLAT
4201 / 2657 / 654
Регистрация: 23.09.2014
Сообщений: 8,958
Записей в блоге: 3
19.11.2019, 23:27
Лучший ответ Сообщение было отмечено Fury67 как решение

Решение

Fury67,
на этих ребрах:
C++
1
2
3
4
5
6
7
8
9
10
11
    unt test[] = {
        0, 1, 1000,
        1, 2, 9999,
        1, 3, 9999,
        1, 4, 9999,
        1, 5, 9999,
        1, 0, 9999,
        1, 0, 9999,
        1, 0, 9999,
        1, 0, 9999
    };
выдает ответ:
C++
81
    std::cout << "0";
правильный ответ 10999
Проверьте у себя.
1
Just Do It!
 Аватар для XLAT
4201 / 2657 / 654
Регистрация: 23.09.2014
Сообщений: 8,958
Записей в блоге: 3
20.11.2019, 00:32
Лучший ответ Сообщение было отмечено Fury67 как решение

Решение

решение: исправил константу 10001 на 0xffffffff
Кликните здесь для просмотра всего текста

больше не экспериментировал.
1
Заяц, просто Заяц.
 Аватар для Fury67
666 / 280 / 156
Регистрация: 12.11.2017
Сообщений: 882
20.11.2019, 01:22  [ТС]
XLAT, спасибо. Недоработка была именно в этом.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
20.11.2019, 01:22
Помогаю со студенческими работами здесь

Обход взвешенного неориентированного графа
Всем привет. Стоит задача обойти и начальной вершины все вершины графа и вернуться в исходную. Граф неориентированный, взвешенный, каждая...

Как в случае связного обыкновенного графа определить длину кратчайшего пути между вершинами
Пусть G = (V,E) -- обыкновенный граф, А(G) -- матрица смежности этого графа, отвечающая нгекоторой нумарции вершин v1, v2,...,vn. ...

Алгоритм Прима: построение min остовного дерева взвешенного связного неориентированного графа (Си -> Python)
задача: Алгоритм Прима. Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа....

Граф. Для каждой пары городов найти длину кратчайшего пути между ними.
Задана система двухсторонних дорог. Для каждой пары городов найти длину кратчайшего пут между ними.

Найти длину кратчайшего пути
Добрый день! у меня задание: найти длину кратчайшего пути: Казалось бы, все очень просто.. можно просто даже по таблице посчитать,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Новые блоги и статьи
сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3
anaschu 06.01.2026
aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ФедосеевПавел 06.01.2026
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .
Модель микоризы: классовый агентный подход 2
anaschu 06.01.2026
репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока
igorrr37 05.01.2026
/ * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru