Tietoverkko

input/code.cpp: In member function 'long long unsigned int Graph::BFS(int)':
input/code.cpp:116:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < neighbors.size(); j++)
                             ~~^~~~~~~~~~~~~~~~~~
input/code.cpp:126:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int i = 0; i < visited.size(); i++)
                                 ~~^~~~~~~~~~~~~~~~
input/code.cpp:132:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for (int k = 0; k < dist[i].size(); k++)
                                         ~~^~~~~~~~~~~~~~~~

#include <iostream>
#include <vector>
#define ull unsigned long long
using namespace std;
 
class Queue
{
private:
    vector<ull> queue;
 
public:
    Queue()
    {
    }
 
    void enqueue(int vertex)
    {
        queue.push_back(vertex);
    }
 
    int dequeue()
    {
        int vertex = queue[0];
        queue.erase(queue.begin());
        return vertex;
    }
 
    bool isempty()
    {
        if (queue.size())
            return false;
        else
            return true;
    }
 
    ~Queue()
    {
        queue.clear();
    }
};
 
class Graph
{
private:
    int **adjMatrix;
    int numVertices;
 
public:
    Graph(int numVertices)
    {
        this->numVertices = numVertices;
        adjMatrix = new int *[numVertices];
        for (int i = 0; i < numVertices; i++)
        {
            adjMatrix[i] = new int[numVertices];
            for (int j = 0; j < numVertices; j++)
            {
                adjMatrix[i][j] = 0;
            }
        }
    }
 
    void addEdge(int i, int j, int x)
    {
        adjMatrix[i][j] = x;
        adjMatrix[j][i] = x;
    }
 
    int getValue(int i, int j)
    {
        return adjMatrix[i][j];
    }
 
    vector<pair<int, ull>> neighbor(int vertex)
    {
        vector<pair<int, ull>> neighbors;
 
        for (int j = 0; j < numVertices; j++)
        {
            if (adjMatrix[vertex][j])
                neighbors.push_back(make_pair(j, adjMatrix[vertex][j]));
        }
        return neighbors;
    }
 
    ull minelement(vector<ull> x, ull start, ull end)
    {
        ull min = x[0];
        for (ull i = start; i < end; i++)
        {
            if (x[i] < x[0])
                min = x[i];
        }
        return min;
    }
 
    ull BFS(int start)
    {
        int vertex;
        ull total = 0;
        vector<bool> visited(numVertices);
        Queue jono;
        vector<vector<ull>> dist(numVertices);
 
        jono.enqueue(start);
        visited[start] = true;
        // dist[start].push_back(0);
 
        // EHDOTUS: Käy läpi VISITED listaan ja lisää niistä kaikista etäisyydet.
 
        while (!jono.isempty())
        {
            vertex = jono.dequeue();
            // cout << "\nAccessing primary vertex: " << vertex << endl;
            vector<pair<int, ull>> neighbors = neighbor(vertex);
            for (int j = 0; j < neighbors.size(); j++)
            {
                if (visited[neighbors[j].first])
                    continue;
                // cout << "Accessing neighboring vertex: " << neighbors[j].first << endl;
                jono.enqueue(neighbors[j].first);
                visited[neighbors[j].first] = true;
                dist[neighbors[j].first] = dist[vertex];
                dist[neighbors[j].first].push_back(neighbors[j].second);
 
                for (int i = 0; i < visited.size(); i++)
                {
                    if (visited[i])
                    {
                        dist[i].push_back(neighbors[j].second);
 
                        for (int k = 0; k < dist[i].size(); k++)
                        {
                            total += minelement(dist[i], k, dist[i].size() + 1);
                        }
                    }
                }
            }
        }
        return total;
    }
 
    ~Graph()
    {
        for (int i = 0; i < numVertices; i++)
        {
            delete[] adjMatrix[i];
        }
        delete[] adjMatrix;
    }
};
 
int main()
{
    long n, a, b, x = 0;
    ull sum;
    cin >> n;
    Graph network(n + 1);
 
    for (int i = 1; i < n; i++)
    {
        cin >> a >> b >> x;
        network.addEdge(a, b, x);
    }
 
    sum = network.BFS(1) / n;
    cout << sum;
}

Test 1

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: RUNTIME ERROR