Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

28.11.2011, 20:06. Просмотров 2745. Ответов 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.11.2011, 20:06
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Кратчайший путь в графе. (C++):

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

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

Как найти НЕ Кратчайший путь в графе ? - C++
Мне нужно найти не кратчайший путь в графе от одной вершины к другой, граф неориентированный, задан списком смежности типа: 5 1 1 2 3...

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

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

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

1
e.b0sh
0 / 0 / 0
Регистрация: 27.11.2011
Сообщений: 5
30.11.2011, 00:29  [ТС] #2
Нашел проблему.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.11.2011, 00:29
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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