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

ACCESS_VIOLATION при решении задачи - C++

Восстановить пароль Регистрация
 
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
25.05.2013, 21:01     ACCESS_VIOLATION при решении задачи #1
Здравствуйте!Тут решал одну простую задачу, но на dl.gsu.by она не проходит последний тест:не пройден 10-й тест. Решение вызвало ошибку ACCESS_VIOLATION

Вот сама задача:

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 2 секунды
Ограничение на память: 16 МБ

Задан неориентированный взвешенный граф G. В графе возможно наличие нескольких ребер между одной и той же парой вершин. Найдите вес кратчайшего пути между двумя заданными вершинами A и B.

Входные данные.

Первая строка входного файла содержит два целых число N (1 ≤ N ≤ 1000) - количество вершин графа и M (1 ≤ M ≤ 100000) - количество ребер графа. В каждой из следующих M строк содержатся ровно три числа a, b, c (1 ≤ a, b ≤ N, 1 ≤ c ≤ 100000). Эти числа описывают ребро, соединяющее вершины с номерами a и b и имеющее вес c. Последние две строки содержат целые числа A и B (1 ≤ A, B ≤ N) - начальную и конечную вершины пути. Вершины нумеруются последовательными натуральными числами от 1 до N.

Выходные данные. Единственная строка выходного файла должна содержать одно целое число, равное весу кратчайшего пути между вершинами A и B в графе G.



Вот мой код (первые 9 тестов проходит успешно):
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <utility>
#include <cstdlib>
#include <climits>
#include <queue>
#include <vector>
 
using namespace std;
 
const long long maxn=1010,maxm=100010;
long long ef[maxm],es[maxm],ev[maxm],nexti[maxm],first[maxn],last[maxn],c,n,m,a,b,i,x,y,z;
vector<long long> d(maxn,LLONG_MAX);
priority_queue<pair<long long,long long>,vector<pair<long long,long long> >,greater<pair<long long,long long> > >q;
 
void prepare()
{
    c=n=m=a=b=0;
}
 
void add(long long v1,long long v2,long long value)
{
    ++c;
    ef[c]=v1;es[c]=v2;ev[c]=value;
    if(!first[v1])  first[v1]=c;
    if(last[v1])    nexti[last[v1]]=c;
    last[v1]=c;
}
 
void input()
{
    scanf("%I64d%I64d",&n,&m);
    for(i=0;i<m;++i)
    {
        scanf("%I64d%I64d%I64d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    scanf("%I64d%I64d",&a,&b);
}
 
void output()
{
    printf("%I64d",d[b]);
}
 
void dist()
{
    d[a]=0;
    q.push(make_pair(0,a));
    while(!q.empty())
    {
        long long to=q.top().second,line=q.top().first;
        q.pop();
        if(line>d[to])  continue;
        for(long long h=first[to];h;h=nexti[h])
        {
            if(line+ev[h]<d[es[h]])
            {
                d[es[h]]=line+ev[h];
                q.push(make_pair(d[es[h]],es[h]));
            }
        }
    }
}
 
 
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    prepare();
    input();
    dist();
    output();
    //system("pause");
}
Выхода за границы массива вроде как нет, деления на 0 я тут не вижу, по памяти всё проходит.Уже битый час сижу, и ошибку найти не могу.Помогите пожлауйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
25.05.2013, 21:26     ACCESS_VIOLATION при решении задачи #2

Не по теме:

Перепутал кнопки ><



Как я понимаю, узнать данные этого теста нет возможности?
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
25.05.2013, 22:22  [ТС]     ACCESS_VIOLATION при решении задачи #3
Toshkarik, да, именно так.Я даже не представляю, на чем он может валится
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
25.05.2013, 22:45     ACCESS_VIOLATION при решении задачи #4
ZaMaZaN4iK, Ну забей нафиг раз 9 тестов прошол, а один нет, 9 из 10 это хороший результат. Возможно баг в самом тесте .
Нет старичок я когда вижу рыжего кролика здорового и читаю твой ник замазанчик сразу чото улыбка на лице появляется непроизвольная, а еще если представляю школьника, то ппц начинаю просто смеятся. Нет старичок ну реально ты меня веселишь. Даже не знаю почему.
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
25.05.2013, 23:15     ACCESS_VIOLATION при решении задачи #5
ZaMaZaN4iK, если нет данных теста, то могу предположить лишь проверить у себя на различных комбинациях граничных условий входных данных...

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

Не по теме:

s/граничных условий/граничных значений

ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
25.05.2013, 23:45  [ТС]     ACCESS_VIOLATION при решении задачи #6
gray_fox, результат показал, что сбой происходит всё таки.Теперь осталось выяснить - почему=)Дело осталось всего-ничего)))
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
25.05.2013, 23:50     ACCESS_VIOLATION при решении задачи #7
ZaMaZaN4iK, ну так
Мой лучший друг-отладчик!
)

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

Не по теме:

Я так понимаю, вы подобрали набор данных, на которых всё падает...

ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
26.05.2013, 00:20  [ТС]     ACCESS_VIOLATION при решении задачи #8
gray_fox, да не особо - просто рандомом забил всё в допустимых пределах.Я заметил, что у меня ввод данных барахлит - не вводятся полностью ребра графа - и всё.пытаюсь найти причину, хотя внешне обычный ввод, что в нём может быть такого...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.05.2013, 00:46     ACCESS_VIOLATION при решении задачи
Еще ссылки по теме:

C++ решении задачи (по Липпману)
Найти ошибку в решении задачи "Шифровка" (acmp) C++
C++ результат не верный при решении задачи

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

Или воспользуйтесь поиском по форуму:
gray_fox
26.05.2013, 00:46     ACCESS_VIOLATION при решении задачи
  #9

Не по теме:

ZaMaZaN4iK, я бы предложил наприсать скрипт\bat-файл, который бы генерировал данные, вызывал приложение и проверял код возврата (надеясь, что подобная валидация не займёт вечность), но у вас в коде обработки ошибок вообще нет, так что это точно не поможет. Просто имея конкретые данные, на которых падает приложение, всё было бы намного проще...

Yandex
Объявления
26.05.2013, 00:46     ACCESS_VIOLATION при решении задачи
Ответ Создать тему
Опции темы

Текущее время: 16:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru