HackerRankでBFSチャレンジを解決しようとしたときに不正なalloc例外が発生しました

Question

Breadth First Search：HackerRankの最短到達範囲ですが、テストに多数のノード/エッジがあると、 。このプログラムは最初のテストで動作するので、実装には何か問題があるとは思いません。だからここ が実装です： （私の最初の質問、インデントのため申し訳ありません）

#include <cmath> 
#include <cstdio> 
#include <vector> 
#include <iostream> 
#include <algorithm> 
#include <queue> 
#include <limits.h> 
using namespace std; 


int main() { 
//test numbers 
int t; 
//the cost 
int cost = 6; 
cin >> t; 
//for each test 
for (int nt = 0; nt < t; ++nt) { 
    int n, e; 
    int snode; 
    queue <int> *que = new queue<int>(); 
    //read the node/edges 
    cin >> n >> e; 
    //distance/visited/parents arrays/adjlist vector 
    int dist[n + 1] = {-1}; 
    bool visited[n + 1] = {false}; 
    int parents[n + 1] = {-1}; 
    vector< vector<int> > adjList(n + 1); 

    //read into the adjlist, unoriented graph, each edge has 6 weight 
    for (int ne = 0; ne < e; ++ne) { 
     int x, y; 
     cin >> x >> y; 
     adjList[x].push_back(y); 
     adjList[y].push_back(x); 
    } 

    //read the starting node 
    cin >> snode; 
    dist[snode] = 0; 

    //do actual bfs 
    que->push(snode); 
    visited[snode] = true; 
    while(!que->empty()) { 
     int c_node = que->front(); 
     que->pop(); 
     for (int i = 0; i < adjList[c_node].size(); ++i) { 
      if (visited[adjList[c_node].at(i)] == false) { 
       que->push(adjList[c_node].at(i)); 
       parents[adjList[c_node].at(i)] = c_node; 
       dist[adjList[c_node].at(i)] = dist[parents[adjList[c_node].at(i)]] + cost; 
       visited[adjList[c_node].at(i)] == true; 
      } 
     } 
    } 

    //print at output the distance from the starting node to each other node 
    //if unreachable, print -1 
    for (int i = 1; i < n + 1; ++i) { 
     if (i == snode) { 

     } else if (dist[i] == 0 && i != snode) { 
      cout << "-1 "; 
     } else { 
      cout << dist[i] << " "; 
     } 
    } 
    cout << "\n"; 
} 
return 0; 
} 

私が何か間違ったことをやって、私は他の誰が、サイトのディスカッションセクションでこの問題について文句を見ていません。 どのように例外がスローされ、どこから来るのを避けることができますか？ ありがとうございました！

Answer 1

私はあなたの例外の原因を正確にはわかりません。私は入力値から（私が推測する）依存しているので、あなたの問題を再現するために私を知らない。多くの入力値は、私が推測します。

しかし、コードの弱点（IMHO）がありますので、私はそれらに注意を向けようとしています。

1）あなたはforサイクル

queue <int> *que = new queue<int>(); 

でstd::queueをALLOCが、あなたはそれを解放することはありません。それはメモリ

2）使用しているの無駄だCスタイルの可変長配列

int dist[n + 1] = {-1}; 
bool visited[n + 1] = {false}; 
int parents[n + 1] = {-1}; 

彼らは、有効なC++標準のコードではありません。標準容器（ std::vectorまたは std::queue）の使用をお勧めします。

3）要素（-1またはfalse）だけのイニシャライザリストでCスタイルの可変長配列を初期化しています。私はあなたの意図が-1とfalseですべてのn+1要素を初期化していたと思います。しかし、この構文は、-1とfalseという配列の最初の要素だけを初期化します。

n+1要素をすべて-1とfalseに初期化する場合は、（標準）コンテナを使用します。例：

std::vector<int> dist(n+1, -1); 
std::vector<bool> visited(n+1, false); 
std::vector<int> parents(n+1, -1); 

4）境界チェックなしで配列にアクセスします。例によって：

cin >> snode; 
dist[snode] = 0; 

snodeはint変数です。負の値、またはnを超える値を挿入すると、その範囲外にdistと書き込んで、メモリを壊滅させます。これは、あなたの "不正なalloc例外"を説明できると思います。

提案：Cスタイルの配列の代わりに標準のコンテナを使用し、境界チェックを実行するat()を代わりに使用してください。[];そう私の悪い英語のため申し訳ありません

cin >> snode; 
dist.at(snode) = 0; 

5）（OK、私は冗談を言っている：これはあなたの弱点の一つではありません。これは私のものです）。