Radi stvarno PP

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <mpi.h>

#define ROW_LENGTH 3

void printMatrix(int **matrix, int m, int n)
{
    int i, j;
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
        {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int getDistance(int **matrix, int *visited, int c, int n)
{
    int i, j, tempDistance = 0, distance = 0;
    visited[c] = 1;

    for (i = 0; i < n; i++)
    {
        // If our city is in the route
        if ((matrix[i][0] == c || matrix[i][1] == c))
        {
            // Check if city is not visited
            int cityId = matrix[i][0] != c ? matrix[i][0] : matrix[i][1];
            if (visited[cityId] == -1)
            {
                visited[cityId] = 1;
                distance += matrix[i][2];
            }
            if (distance == 0) return distance;
            else
            {
                distance += getDistance(matrix, visited, cityId, n);
            }
        }
    }

    return distance;
}

int findCost(int **matrix, int X, int Y,int n, int i) {
    for(i = 0; i < n; i++) if ((matrix[i][0] == X && matrix[i][1] == Y) || (matrix[i][0] == Y && matrix[i][1] == X)) return matrix[i][2];
    return 99999;
}
int calculateMaxLocalDistance(int **matrix, int startI, int stopI, int n, int rank)
{
    int maxLocalDistance = -1, distance = 0;

    int w, ww, flag = 0;

    for(w = startI; w <= stopI; w++)
    {
        for(ww = 1; ww <= n; ww++)
        {
            int dist[n],prev[n],selected[n],i,m,min,start,d,j;
            char path[n];
            int target = ww;
            for(i=1;i<n;i++)
            {
                dist[i] = 99999;
                selected[i] = 0;
            }
            start = w;
            selected[start]=1;
            dist[start] = 0;
            while(selected[target] ==0)
            {
                min = 99999;
                m = 0;
                for(i=1;i< n;i++)
                {
                    int findedCost = findCost(matrix, start, i, n, 0);
                    d = dist[start] + findedCost;
                    if(d < dist[i]&&selected[i]==0)
                    {
                        dist[i] = d;
                    }
                    if(min>dist[i] && selected[i]==0)
                    {
                        min = dist[i];
                        m = i;
                    }
                }
                start = m;
                selected[start] = 1;
            }

            distance = dist[target];

            if (distance > maxLocalDistance && distance < 100)
            {
                maxLocalDistance = distance;
            }
        }
    }



    printf("Max local distance: %d\n", maxLocalDistance);
    return maxLocalDistance;
}

void doWork(int **matrix, int n, int rank, int size)
{
    // Set indexes
    int maxDistance;
    int batchCount = n / size;
    int startI = rank * batchCount + 1;
    int stopI = startI + batchCount;
    if (rank != 0) startI++;
    if (rank == size - 1 && n % 2 != 0) stopI++;

    // Calculate max route where start city is in batch range startI-stopI
    int maxLocalDistance = calculateMaxLocalDistance(matrix, startI, stopI, n, rank);

    // Do reduction to get longest calculated distances between cities
    MPI_Reduce(&maxLocalDistance, &maxDistance, 1, MPI_INT, MPI_MAX, 0, MPI_COMM_WORLD);

    // Print the result
    if (rank == 0) printf("%d\n", maxDistance);
}

int main(int argc, char **argv)
{
    int rank, size;
    int i, j, n, N;

    MPI_Init(&argc, &argv);

    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);

    int **matrix = (int**)malloc(n * sizeof(int*));
    for (i = 0; i < n; i++) matrix[i] = (int*)malloc(ROW_LENGTH * sizeof(int));

    int **matrixG = (int**)malloc(n * sizeof(int*));
    for (i = 0; i < n; i++) matrixG[i] = (int*)malloc(ROW_LENGTH * sizeof(int));

    // Read input data
    if (rank == 0)
    {
        scanf("%d", &N);
        n = N;

        for (i = 0; i < n - 1; i++) scanf("%d %d %d", &matrix[i][0], &matrix[i][1], &matrix[i][2]);
    }

    // Broadcast input data
    MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
    for (i = 0; i < n - 1; i++) MPI_Bcast(matrix[i], ROW_LENGTH, MPI_INT, 0, MPI_COMM_WORLD);

    MPI_Barrier(MPI_COMM_WORLD);

    //printMatrix(matrix, n - 1, ROW_LENGTH);


    // doWork
    // Idea is to check all possible combinations in next way
    // Because we have N cities we will create batches N / size of cities to check
    // and each city process will calculate longest posible route for its batch
    // In the end, we will get the best one by reduction.

    // Do work returns maxLocalDistance -> after this step, we must calculate global maximum for all processes.
    doWork(matrix, n - 1, rank, size);

    MPI_Finalize();

    return 0;
}