C++ STL Breadth first search

Question

#include <queue> 
#include <vector> 
#include <iostream> 
using namespace std; 


int main() { 
int x; 
cin >> x; 
for(int tt=0;tt<x;tt++) 
    { 
    //cout << "HI" << endl; 
    int n, m; 
    cin >> n >> m; 
    vector< vector<int> > g(n); 
    for(long j =0; j< m;j++) 
     { 
     int u , v; 
     cin >> u >> v; 

     g[u-1].push_back(v-1); 
     g[v-1].push_back(u-1); 

    } 

    int s; 
    cin >> s; 

    vector<int> out(n,-1); 
    vector<int> visited(n,0); 
    int value = 0; 
    queue<int> q; 
    q.push(s-1); 
    q.push(-1); 
    visited[s-1] =1; 
    int flag =0; 
    while(!q.empty()) 
     { 
     int v = q.front(); 
     out[v] = value; 
     q.pop(); 
     if(v == -1) 
      { 
      value += 6; 
     } 
     else{ 
      for(vector<int>::iterator it = g[v].begin(); it != g[v].end();it++) 
       { 
       if(visited[*it] == 0) 
        { 
        q.push(*it); 
        visited[*it] =1; 
       } 
      } 
     } 

    } 
    //cout << "hello" << endl; 
    for(int k =0; k<n; k++) 
     { 
     if(k!= s-1) 
      { 
      cout << out[k] << " "; 
     } 
    } 
    cout << endl; 
    //cout << "yo"; 
} 
//cout << "you"; 
return 0; 
} 

Этот код хорошо работает, если начальный узел имеет только соседний уровень 1-го уровня. Для того, чтобы заставить его работать во всех случаях, когда я изменить

if(v == -1) 
{ 
     value += 6; 
} 

в

if(v == -1) 
{ 
    value += 6; 
    if(!q.empty()) 
      q.push(-1); 
} 

она даже не работает для всех testcases в настоящее время. Затем программа прерывается и сообщение об ошибке от хакера ранга * Ошибка в `решение": двойной бесплатно или повреждение (уходит): 0x00000000009e5cf0 *

Я не могу понять, почему это происходит. Почему существует проблема в цикле for, когда я обрабатываю очередь.

Ссылка на вопрос о хакерранке.

https://www.hackerrank.com/challenges/bfsshortreach

Answer 1

Вам нужно

1. избавиться от value, не требуется.
2. Вектор вне пределов доступа был там. что из [-1]?
3. собственный отступ
4. Bfs всегда посещает уровень мудрого. Вам не нужно поддерживать его, нажав отрицательное значение в очереди.

Правильный код:

#include <queue> 
#include <vector> 
#include <iostream> 
using namespace std; 


int main() { 
    int x,n, m,u , v; 
    cin >> x; 
    for(int tt=0;tt<x;tt++){ 
     cin >> n >> m; 
     vector< vector<int> > g(n); 
     for(long j =0; j< m;j++){ 
      cin >> u >> v; 
      g[u-1].push_back(v-1); 
      g[v-1].push_back(u-1); 
     } 

     int s; 
     cin >> s; 

     vector<int> out(n,-1); 
     vector<bool> visited(n,0); 
     queue<int> q; 
     q.push(s-1); 
     visited[s-1] =1; 
     out[s-1]=0; 

     while(!q.empty()){ 
      int v = q.front(); q.pop(); 

      for(vector<int>::iterator it = g[v].begin(); it != g[v].end();it++){ 
       if(visited[*it] == 0){ 
        q.push(*it); 
        visited[*it] =1; 
        out[*it]=out[v]+6; 
       } 
      } 

     } 
     for(int k =0; k<n; k++){ 
      if(k!= s-1){ 
       cout << out[k] << " "; 
      } 
     } 
     cout << endl; 
    } 
    return 0; 
}