Блог

Главная - Вопросы по программированию - Как изменение типа данных массива с int на long long и INT_MAX на LLONG_MAX в коде C привело к ошибке во время выполнения?

Как изменение типа данных массива с int на long long и INT_MAX на LLONG_MAX в коде C привело к ошибке во время выполнения?

#c #pointers #integer #runtime-error #long-long

#c #указатели #целое число #ошибка во время выполнения #длинный-длинный

Вопрос:

Значения в моих входных файлах testcase были такими, что в какой-то момент в коде значения будут превышать емкость int , поэтому я решил изменить тип данных этого конкретного массива, содержащий это значение, большее INT_MAX, с int на long long и изменить максимальные значения в коде на LLONG_MAX с INT_MAX, чтобыэто сравнение во время выполнения не дает неправильного ответа.

Однако теперь код, похоже, застрял с ошибкой времени выполнения еще до того, как попал в упомянутый тестовый случай. Теперь он терпит неудачу в случае, который он использовал для передачи, когда все значения были ориентированы на int. Я не понимаю, как это возможно.

Тестовый пример, который проходит с помощью int, но завершается неудачей с помощью ll, является:

 100 50
1 23 133
1 87 16
2 9 78
3 12 117
3 39 19
5 25 219
5 47 130
5 97 157
6 50 114
9 11 25
9 39 227
10 45 187
10 77 120
12 19 85
13 43 247
14 16 4
15 33 223
16 33 1
19 69 204
20 35 119
20 43 213
20 86 19
22 40 233
23 33 61
23 79 152
26 89 213
27 57 129
28 42 220
31 68 84
31 69 183
32 39 145
32 100 117
33 49 198
34 48 78
37 66 200
37 91 77
39 44 235
41 70 109
42 92 33
44 74 196
48 73 26
51 57 216
53 70 158
63 98 220
66 72 148
80 93 150
81 99 54
83 84 129
83 89 177
95 100 16

Ниже приведен код, который выдает ошибку при этом tc.

 #include<bits/stdc  .h>
using namespace std;

# define ll long long int

ll update, previous; 
set<pair<ll, int>> dist;
auto it=dist.begin();
int ind=0, n, i, j;
pair<ll, int>p;

void dij(vector<pair<int, ll>> tree[], bool decided[], ll d[], int path[]) {
    ind=0;
    while(!dist.empty()) {
        it=dist.begin();
        if(it==dist.end()) return;
        ind=it->second;
        dist.erase(it);
        decided[ind]=1;
        for(j=0; j<tree[ind].size(); j  ) {
            update=d[ind] tree[ind][j].second;
            previous=d[tree[ind][j].first];
            if(update<previous) {
                p=make_pair(previous, tree[ind][j].first);
                dist.erase(dist.find(p));
                p=make_pair(update, tree[ind][j].first);
                dist.insert(p);
                path[tree[ind][j].first]=ind;
            }
            d[tree[ind][j].first]=min(update, previous);
        }
    }
}

int main()
{
    ll edges;
    ll x, y, weight;
    cin>>n>>edges;
    vector<pair<int, ll>> graph[n];
    for(i=0; i<edges; i  ) {
        cin>>x>>y>>weight;
        x--; y--;
        graph[x].push_back({y, weight});
        graph[y].push_back({x, weight});
    }
    int src=1;
    src--;
    ll d[n];
    for(i=0; i<n; i  ) {
        if(src==i) {
            dist.insert({0, i});
            d[i]=0;
        }
        else {
            dist.insert({LLONG_MAX, i});
            d[i]=LLONG_MAX;
        }
    }
    bool decided[n]={0};
    int path[n]={-1};
    for(int i=1; i<n; i  ) path[i]=-2;
    dij(graph, decided, d, path);
    if(path[n-1]==-2) cout<<-1;
    else {
        vector<int> s;
        int final=n-1;
        while (final!=-1) {
            s.push_back(final);
            final=path[final];
        }
        reverse(s.begin(), s.end());
        for(auto pi:s) cout<<pi 1<<" ";
    }
    cout<<endl;
}

Ниже приведен код, который выдает правильный вывод для этого tc.

 #include<bits/stdc  .h>
using namespace std;

# define ll long long int

ll update, previous; 
set<pair<ll, int>> dist;
auto it=dist.begin();
int ind=0, n, i, j;
pair<ll, int>p;

void dij(vector<pair<int, ll>> tree[], bool decided[], int d[], int path[]) {
    ind=0;
    while(!dist.empty()) {
    it=dist.begin();
    if(it==dist.end()) return;
    ind=it->second;
    dist.erase(it);
    decided[ind]=1;
    for(j=0; j<tree[ind].size(); j  ) {
        update=d[ind] tree[ind][j].second;
        previous=d[tree[ind][j].first];
        if(update<previous) {
            p=make_pair(previous, tree[ind][j].first);
            dist.erase(dist.find(p));
            p=make_pair(update, tree[ind][j].first);
            dist.insert(p);
            path[tree[ind][j].first]=ind;
        }
        d[tree[ind][j].first]=min(update, previous);
    }
    }
}

int main()
{
    ll edges;
    ll x, y, weight;
    cin>>n>>edges;
    vector<pair<int, ll>> graph[n];
    for(i=0; i<edges; i  ) {
        cin>>x>>y>>weight;
        x--; y--;
        graph[x].push_back({y, weight});
        graph[y].push_back({x, weight});
    }
    int src=1;
    src--;
    int d[n];
    for(i=0; i<n; i  ) {
        if(src==i) {
            dist.insert({0, i});
            d[i]=0;
        }
        else {
            dist.insert({INT_MAX, i});
            d[i]=INT_MAX;
        }
    }
    bool decided[n]={0};
    int path[n]={-1};
    for(int i=1; i<n; i  ) path[i]=-2;
    dij(graph, decided, d, path);
    if(path[n-1]==-2) cout<<-1;
    else {
        vector<int> s;
        int final=n-1;
        while (final!=-1) {
            s.push_back(final);
            final=path[final];
        }
        reverse(s.begin(), s.end());
        for(auto pi:s) cout<<pi 1<<" ";
    }
    cout<<endl;
}

Единственным различием в 2 кодах являются следующие строки:

void dij(vector<pair<int, ll>> tree[], bool decided[], ll d[], int path[])

void dij(vector<pair<int, ll>> tree[], bool decided[], int d[], int path[])

ll d[n];

int d[n];

dist.insert({LLONG_MAX, i})

dist.insert({INT_MAX, i})

d[i]=LLONG_MAX

d[i]=INT_MAX

Может кто-нибудь, пожалуйста, указать, как это создает следующую ошибку, которую я прочитал, связанную с «выделением памяти там, где я не должен» или «попыткой выполнить удаление со значением указателя, которое не было получено из new». Что вызывает эту проблему и как я должен ее решить?

 free(): invalid pointer
Aborted (core dumped)

Комментарии:

1. Зачем использовать нестандартные и рискованные массивы переменной длины, когда вы знаете std::vector ?

2. int d[n]; — Чтобы добавить к предыдущему комментарию, который вы уже используете std::vector , так почему вы не использовали его и здесь? Похоже, вы не знаете, для чего используются векторы.

3. решит ли проблему использование вектора вместо массива?

4. Использование векторов даст вам шанс на победу в решении проблемы. С помощью vector у вас есть at() функция, которая проверяет граничные условия. Для этих нестандартных массивов переменной длины такого нет. И в любом случае, любому, кто использует Visual C , который попытается протестировать ваш код, все равно придется его изменить. Было бы лучше, если бы вы изменили свой код, чтобы не использовать какие-либо VLA и использовать vector.

5. Добро пожаловать в мир C . То, что код «работает», не означает, что он правильный. В C есть нечто, называемое «неопределенное поведение».

Ответ №1:

Проблема действительно была связана с long long , и именно поэтому код с int выполнялся нормально, потому что тот факт, что update это создало бы переполнение, поскольку переменная представляет собой сумму двух long long переменных типа, которым было бы присвоено максимальное значение LLONG_MAX main() , был упущен.

Поскольку long long не может вместить 2*LLONG_MAX , он не удерживал и не находил это значение в наборе пар, используемых в качестве минимальной кучи. Таким образом, итератор, указывающий на конец набора, и стирание set.end() приведет к неопределенному поведению в long long коде, ориентированном на тип данных, тогда как в ориентированном коде этого не int было бы.

Замена LLONG_MAX на 1e18 instead в коде решила проблему, и код выполняется для всех тестовых файлов плавно.

Кроме того, чтобы прояснить все причины, которые были указаны в комментариях, я подумал, что должен уточнить, что отсутствие проверки dist.find(p) наличия и не указывает на конец набора перед выполнением dist.erase(dist.find(p)) не создаст никаких проблем. Это связано с тем, что это алгоритм Дейкстры, и столько раз, сколько update окажется меньше previous , узел, для которого вычисляется это обновленное расстояние, из источника всегда будет присутствовать в наборе в паре с расстоянием previous . Это связано с тем, что все узлы изначально вводятся со значением 10e8 и обновляются по мере нахождения значений в последовательных итерациях цикла while.

Ниже приведен рабочий код, единственное отличие заключается в том, что вместо LLONG_MAX я использовал 1e18 и он отлично работает со всеми тестовыми файлами, включая тот, который я упомянул в вопросе как проблематичный.

 #include<bits/stdc  .h>
using namespace std;

# define ll long long int

ll update, previous; 
set<pair<ll, int>> dist;
auto it=dist.begin();
int ind=0, n, i, j;
pair<ll, int>p;

void dij(vector<pair<int, ll>> tree[], bool decided[], ll d[], int path[]) {
    ind=0;
    while(!dist.empty()) {
        it=dist.begin();
        if(it==dist.end()) return;
        ind=it->second;
        dist.erase(it);
        decided[ind]=1;
        for(j=0; j<tree[ind].size(); j  ) {
            update=d[ind] tree[ind][j].second;
            previous=d[tree[ind][j].first];
            if(update<previous) {
                p=make_pair(previous, tree[ind][j].first);
                //cout<<p.first<<" intermediate "<<p.second<<endl;
                dist.erase(dist.find(p));
                p=make_pair(update, tree[ind][j].first);
                dist.insert(p);
                path[tree[ind][j].first]=ind;
            }
            d[tree[ind][j].first]=min(update, previous);
        }
    }
}

int main()
{
    ll edges;
    ll x, y, weight;
    cin>>n>>edges;
    vector<pair<int, ll>> graph[n];
    for(i=0; i<edges; i  ) {
        cin>>x>>y>>weight;
        x--; y--;
        graph[x].push_back({y, weight});
        graph[y].push_back({x, weight});
    }
    int src=1;
    src--;
    ll d[n];
    for(i=0; i<n; i  ) {
        if(src==i) {
            dist.insert({0, i});
            d[i]=0;
        }
        else {
            dist.insert({1e18, i});
            d[i]=1e18;
        }
    }
    bool decided[n]={0};
    int path[n]={-1};
    for(int i=1; i<n; i  ) path[i]=-2;
    dij(graph, decided, d, path);
    if(path[n-1]==-2) cout<<-1;
    else {
        vector<int> s;
        int final=n-1;
        while (final!=-1) {
            s.push_back(final);
            final=path[final];
        }
        reverse(s.begin(), s.end());
        for(auto pi:s) cout<<pi 1<<" ";
    }
    cout<<endl;
}

Вот выходные данные для тестового файла в вопросе:

Ввод

 100 50
1 23 133
1 87 16
2 9 78
3 12 117
3 39 19
5 25 219
5 47 130
5 97 157
6 50 114
9 11 25
9 39 227
10 45 187
10 77 120
12 19 85
13 43 247
14 16 4
15 33 223
16 33 1
19 69 204
20 35 119
20 43 213
20 86 19
22 40 233
23 33 61
23 79 152
26 89 213
27 57 129
28 42 220
31 68 84
31 69 183
32 39 145
32 100 117
33 49 198
34 48 78
37 66 200
37 91 77
39 44 235
41 70 109
42 92 33
44 74 196
48 73 26
51 57 216
53 70 158
63 98 220
66 72 148
80 93 150
81 99 54
83 84 129
83 89 177
95 100 16

Вывод участника

 -1

Ответ жюри

 -1

Ссылка на отправку — Дейкстра

Комментарии:

1. Changing LLONG_MAX to 1e18 solved the problem нет, вам не разрешено изменять стандартные значения макросов

2. Я имел в виду заменить LLONG_MAX в коде на 1e18

3. Я думал, это очевидно… кроме того, в ответе также есть код, поэтому я не думал, что это понятно, но я обязательно отредактирую его на «заменить» вместо «изменить», чтобы никто больше не запутался…

4.Вот ваш ответ, написанный на стандартном C .