Возможно, неправильно обрабатывает векторные массивы (BFS находит кратчайшее расстояние до всех узлов) - PullRequest
Новая
       25

Возможно, неправильно обрабатывает векторные массивы (BFS находит кратчайшее расстояние до всех узлов)

0 голосов
/ 02 мая 2018

Эта проблема больше связана с программированием, чем с конкурентным программированием. Я относительно новичок, когда дело доходит до написания программ с использованием теории графов. Я объяснил вопрос ниже. Я закодировал решение с помощью необходимой логики apt, но по некоторым причинам мой вывод не соответствует тестовым сценариям. Пожалуйста, помогите мне с моим кодом, приведенным ниже. (ПРИМЕЧАНИЕ: я включил тестовые случаи, ожидаемый вывод и вывод, который я получаю в конце кода)

Я кратко опишу постановку задачи:

Учитывая график, где каждое ребро имеет вес 6 единиц (не нужно подключаться), используйте Поиск в ширину, чтобы найти кратчайшее расстояние от исходного узла до всех других узлов.

Ссылка на проблему: https://www.hackerrank.com/challenges/bfsshortreach/problem

Формат ввода:

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

Первая строка содержит два разделенных пробелом целых числа n и m, количество узлов и ребер в графе.

Каждая строка из m последующих строк содержит два разделенных пробелом целых числа u и v, описывающих ребро, соединяющее узел u с узлом v.

Последняя строка содержит одно целое число s, обозначающее индекс начального узла для процедуры BFS.

Мой код: 

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

void addedge(int u,int v, vector <int> edges[]) {
    edges[u].push_back(v);
    edges[v].push_back(u); 
}

void bfs(int n,int m,vector <int> edges[],int s) {
    queue <int> q;
    vector <int> d(n+1);
    for(int o=0;o<n;o++) d[o]=-1;
    q.push(s); d[s]=0;
    while(!q.empty())
    {
        int temp=q.front(); q.pop();
        for(auto x : edges[temp])
        {
            if(d[x] == -1) { d[x]=d[temp] + 6; q.push(x);}
        }
    }
    for(auto l=0;l<d.size();l++) cout<<d[l]<<" ";


}
    int main() {
        int q,n,i,m,s,t,u;
        cin>>q;
        for(i=0;i<q;i++)
        {
        cin>>n>>m;
        vector <int> edges[n];
        for(i=0;i<m;i++)
        { 
        cin>>t>>u; 
        addedge(t,u,edges);
        int s;
        cin>>s;
        bfs(n,m,edges,s); 
        cout<<"\n";
        }

    }
    return 0;
}

Input:

2
4 2
1 2
1 3
1
3 1
2 3
2

Expected Output:

6 6 -1
-1 6

Actual Output:

-1 0 6 -1 0 
-1 6 12 0 0
...