Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.84
e.b0sh
0 / 0 / 0
Регистрация: 27.11.2011
Сообщений: 5
#1

Кратчайший путь в графе. - C++

28.11.2011, 20:06. Просмотров 2575. Ответов 1
Метки нет (Все метки)

Такая задача:
Дан ориентированный взвешенный ациклический граф. Требуется найти в нем кратчайший путь
из вершины s в вершину t.
Первая строка входного файла содержит четыре целых числа n, m, s и t — количество вершин,
дуг графа, начальная и конечная вершина соответственно. Следующие m строк содержат описания
дуг по одной на строке. Ребро номер i описывается тремя натуральными числами b_i, e_i и w_i —
началом, концом и длиной дуги соответственно (1 <= b_i, e_i <= n, |wi| <= 1000).
Входной граф не содержит циклов и петель.
1 <= n <= 100 000, 0 <= m <= 200 000.
Первая строка выходного файла должна содержать одно целое число — длину кратчайшего пути
из s в t. Если пути из s в t не существует, выведите «Unreachable».

Мне нужно сдать её в автоматическую систему проверки, где задача проходит 30-50 тестов(точное число тестов для конкретной задачи неизвестно). И если на каком-то тесте задача выполняется слишком долго или выдает неверный ответ, то моё решение не засчитывается. У меня валится на 33ем тесте... Уже как только не тестил, всё нормально работает. Помогите кто-нибудь разобраться в чем ошибка.

Алгоритм заключается в следующем: По умолчанию расстояние до каждой вершины в данном графе бесконечность (INF), кроме стартовой вершины, до неё расстояние равно 0. Значит, топологически сортируем наш граф, затем в порядке топологической сортировки проходим по графу от стартовой вершины до конечной. И делаем релаксацию ребер (вроде так называется).

Короче даже если ничего непонятно, кому нечего делать может помочь найти такие тесты, при которых программа будет выдавать неверный ответ. Причем именно неверный ответ, если программа будет аварийно завершатся из-за переполнения стека вызовов - ничего страшного.

C++
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
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
 
#define K topological[i]
 
using namespace std;
 
const int N = 100001, INF = 200000001;
enum COLOR {WHITE, BLACK};
 
struct node
{
    int number;
    COLOR color;
    vector<node*> next;
    vector<int> weights;
    int path;
};
 
int n, m, s, t;
node graph[N];
vector<int> topological;
 
void dfs(int v)
{
    if (graph[v].color == BLACK)
        return;
    for (unsigned i = 0; i < graph[v].next.size(); ++i)
        dfs(graph[v].next[i]->number);
    topological.push_back(v);
    graph[v].color = BLACK;
}
 
void topsort()
{
    for (int i = 1; i <= n; ++i)
        dfs(i);
    reverse(topological.begin(), topological.end());
}
 
int main()
{
    ifstream in("shortpath.in.txt");
    ofstream out("shortpath.out.txt");
 
    int i, u, v, w;
    in >> n >> m >> s >> t;
    for (i = 1; i <= n; ++i)
    {
        graph[i].number = i;
        graph[i].path = INF;
        graph[i].color = WHITE;
    }
    graph[s].path = 0;
    for (i = 0; i < m; ++i)
    {
        in >> u >> v >> w;
        graph[u].next.push_back(&graph[v]);
        graph[u].weights.push_back(w);
    }
    topsort();
    for (i = 0; graph[K].number != s && graph[K].number != t; ++i);
    if (graph[K].number == t && graph[K].number != s)
        out << "Unreachable";
    else
    {
        for (; graph[K].number != t; ++i)
            for (unsigned j = 0; j < graph[K].next.size(); ++j)
                graph[K].next[j]->path = min(graph[K].path + graph[K].weights[j], graph[K].next[j]->path);
        if (graph[K].path < INF)
            out << graph[K].path;
        else
            out << "Unreachable";
    }
 
    in.close();
    out.close();
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.11.2011, 20:06     Кратчайший путь в графе.
Посмотрите здесь:

Кратчайший путь в графе(Рекурсия) - C++
Я реализовал программу с помощью алгоритма флойда.Препод придрался к тому что я реализовал без рекурсии. Помогите изменить прогу под...

Найдите кратчайший путь в графе - C++
Создайте граф согласно своего варианта в среде С + +, длины путей задайте самостоятельно, найдите кратчайший путь в графе, используя...

Кратчайший путь коня с++ - C++
помогите пожалуйста написать алгоритм кротчайшего пути коня на шахматной доске из А в Б

Графы кратчайший путь ! - C++
Помогите написать функцию для поиска кратчайшего пути между вершинами которые задаются с клавы я написал правда получилось что это...

Как найти кратчайший путь в лабиринте? - C++
Чтобы найти кратчайший путь в лабиринте использую волновой алгоритм, его сделал, но вот кратчайший путь не получается восстановить. ...

Найти кратчайший путь из вершины u в вершину v - C++
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем сможет :sorry: (следующие задачи через обходы в глубину и...

Найти кратчайший путь шахматного короля - C++
Здравствуйте, имеется задача: Есть шахматное поле NxM N, M ≤ 10^9 На шахматном поле отмечено два прямоугольника размерами не менее...

Графы, расположить людей по билетам, кратчайший путь - C++
Здравствуйте. На соревнованиях codeforces я часто замечаю, что больше половины задач на тему графов, где нужно находить кратчайший путь или...

Обогнуть остров, выбрав кратчайший путь вокруг острова - C++
Во входном файле находятся: число N, задающее количество вершин многоугольника и далее координаты вершин многоугольника в виде списка x , y...

Кратчайший путь до какой-то координаты. Ошибка std::bad_alloc - C++
На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная...

С помощью метода волны найти кратчайший путь из одной клетки в другую (ход конём) - C++
Пытаюсь решить такую задачу: с помощью метода волны нужно найти кратчайший путь из одной клетки в другую. Проблема состоит в том, что я...

Найти кратчайший путь в лабиринте, который представлен в виде составного куба заданного размера - C++
Найти кратчайший путь в лабиринте, который представлен в виде составного куба NxNxN, состоящего из маленьких кубиков. Все кубики...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
e.b0sh
0 / 0 / 0
Регистрация: 27.11.2011
Сообщений: 5
30.11.2011, 00:29  [ТС]     Кратчайший путь в графе. #2
Нашел проблему.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru