Блог

Извините за любые неудобства, я новичок в C и застрял с пустым набором… Спасибо за полезные комментарии, которые помогли мне понять, в чем проблема

Я написал код на C для вопроса, в котором мне нужно использовать алгоритм кратчайшего пути Дейкстры за n * log (n) время, и поэтому я использую набор пар для получения вершины с наименьшим расстоянием от исходной вершины. Код не выдавал никаких ошибок во время выполнения, но и не выдавал выходных данных. Поэтому, чтобы увидеть, где он застрял, я использовал операторы cout в определенных точках кода и понял, что код останавливает выполнение сразу после оператора erase .

Оператор используется в коде для удаления первой пары в наборе, и поэтому итератор, указывающий на set.begin() набор, задается в качестве аргумента. Ранее это было написано в формате set.erase(iterator) , но после поиска этой проблемы в stack overflow я нашел кого-то, кто сказал, что iterator=set.erase(итератор) решит проблему. Я попробовал это, и он все еще застревал на этой строке, не останавливая выполнение и не возвращаясь к терминалу и не выдавая ошибку времени выполнения. Я не знаю, что с этим не так, поэтому я подумал, что получу некоторую помощь здесь.

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

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

# define _z ios_base::sync_with_stdio(false); cin.tie(NULL);
# define ll long long int
#define mod 1000000007

int n;
set<pair<int, int>> dist;

void dij(vector<pair<int, int>> tree[], int decided[], int d[], vector<int>path[]) {
    int mindist=INT_MAX, ind=0;
    auto it=dist.begin();
    ind=it->second;
    cout<<"inbetween"<<endl;
    dist.erase(it);
    cout<<"inbetween"<<endl;
    decided[ind]=1;
    for(int i=0; i<tree[ind].size(); i  ) {
        int update=d[ind] tree[ind][i].second;
        int previous=d[tree[ind][i].first];
        if(update<previous) {
            pair<int, int>p=make_pair(previous, tree[ind][i].first);
            dist.erase(dist.find(p));
            p=make_pair(update, tree[ind][i].first);
            dist.insert(p);
            path[tree[ind][i].first]=path[ind];
            cout<<*path[tree[ind][i].first].begin()<<endl;
            path[tree[ind][i].first].push_back(tree[ind][i].first);
        }
        d[tree[ind][i].first]=min(update, previous);
    }
}

int main()
{
    int edges;
    cin>>n>>edges;
    vector<pair<int, int>> graph[n];
    set<pair<int, int>> dist;
    for(int i=0; i<edges; i  ) {
        int x, y, weight;
        cin>>x>>y>>weight;
        x--; y--;
        graph[x].push_back({y, weight});
        graph[y].push_back({x, weight});
    }
    int src=1;
    //cin>>src;
    cout<<"here"<<endl;
    src--;
    int d[n];
    for(int 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;
        }
    }
    int decided[n]={0};
    vector<int> path[n];
    path[src].push_back(src);
    for(int i=0; i<n; i  ) dij(graph, decided, d, path);
    if(path[n-1].begin()==path[n-1].end()) cout<<-1<<endl;
    for(auto it=path[n-1].begin(); it!=path[n-1].end(); it  ) cout<<*it 1<<" ";
    cout<<endl;
}
 

Изображение работающего кода: обратите внимание, что выделенные строки являются проблемными, в той части кода, которая застревает, не существует манипуляций с итератором, и итератор не обращается снова после стирания.

Он печатает только строку перед операцией erase и не печатает строку после…

Проблема, как сообщил пользователь4581301 в комментариях, заключалась в том, что итератор указывал на end() набора, что означает, что набор был пустым, поскольку он был инициализирован для указания на begin() набора. Таким образом, итератор с недостаточной привязкой был разыменован, что привело к неопределенному поведению (это означает, что он не обязательно может выдавать ошибку во время выполнения, а скорее предоставлять выходные данные при разыменовании). Хотя программа, таким образом, застревает на этой строке в результате этого недопустимого доступа.

Ошибка в коде заключалась в том, что set был определен глобально, но затем был уточнен с тем же именем внутри main, это означало, что когда значения заполняются в наборе внутри main, они заполняются в наборе, который был определен в main, а не в том, который определен глобально. Но при обращении к набору в функции dij осуществляется доступ к глобальному набору, который на самом деле пуст!

Удаление переопределения в main решило бы проблему.

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

# define _z ios_base::sync_with_stdio(false); cin.tie(NULL);
# define ll long long int
#define mod 1000000007

int n;
set<pair<int, int>> dist;

void dij(vector<pair<int, int>> tree[], int decided[], int d[], vector<int>path[]) {
    int mindist=INT_MAX, ind=0;
    auto it=dist.begin();
    if(it==dist.end()) return;
    ind=it->second;
    dist.erase(it);
    decided[ind]=1;
    for(int i=0; i<tree[ind].size(); i  ) {
        int update=d[ind] tree[ind][i].second;
        int previous=d[tree[ind][i].first];
        if(update<previous) {
            pair<int, int>p=make_pair(previous, tree[ind][i].first);
            dist.erase(dist.find(p));
            p=make_pair(update, tree[ind][i].first);
            dist.insert(p);
            path[tree[ind][i].first]=path[ind];
            path[tree[ind][i].first].push_back(tree[ind][i].first);
        }
        d[tree[ind][i].first]=min(update, previous);
    }
}

int main()
{
    int edges;
    cin>>n>>edges;
    vector<pair<int, int>> graph[n];
    for(int i=0; i<edges; i  ) {
        int x, y, weight;
        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(int 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;
        }
    }
    int decided[n]={0};
    vector<int> path[n];
    path[src].push_back(src);
    for(int i=0; i<n; i  ) dij(graph, decided, d, path);
    if(path[n-1].begin()==path[n-1].end()) cout<<-1<<endl;
    for(auto it=path[n-1].begin(); it!=path[n-1].end(); it  ) cout<<*it 1<<" ";
    cout<<endl;
}
 

Таким образом, приведенный выше код работает отлично. Ниже приведен скриншот вывода рабочего кода:

Вот некоторые из ссылок, приведенных в комментариях, которые помогли:

1. https://en.cppreference.com/w/cpp/language/ub (неопределенное поведение)
2. https://ideone.com/5NY0q3 (код, который доказал, что начало указывает на конец)
3. https://en.cppreference.com/w/cpp/container/vector/erase (о стирании)
4. https://codeforces.com/contest/20/problem/C (постановка задачи, к которой относится код)

P.S. Код находит путь, по которому можно получить кратчайшее расстояние между вершиной 1 и вершиной n графа с взвешенными ребрами, в O(n* log(n)).

Спасибо.