Помогите пожалуйста найти ошибку в программе

[leksi223]

Условия задачи: Имеются n городов. Некоторые из них соединены двусторонними дорогами, причем для каждой дороги известна максимальная масса груза, который можно по ней везти одним транспортным средством. Напишите программу для определения минимального числа поездок, которое придется совершить из города А в город В, чтобы доставить х тонн продукции при условии, что предприниматель использует только одну фуру грузоподъемностью 20 тонн. При входных данных: 5 городов, грузоподъемность 40, матрица смежности: 0 15 0 0 0 15 0 10 30 0 0 10 0 0 20 0 30 0 0 10 0 0 20 10 0 Из города 0 в город 4, должно получится 4 дороги. А программа считает 6

 #include <limits.h>

#define MAXN 100 // Максимальное количество городов
#define MAX_WEIGHT 20 // Максимальная грузоподъемность фуры

// Функция для поиска минимального числа поездок с использованием BFS
int minTrips(int n, int graph[MAXN][MAXN], int start, int end, int totalWeight) {
    int trips[MAXN];
    for (int i = 0; i < n; i++) {
        trips[i] = INT_MAX;
    }

    int queue[MAXN];
    int front = 0, rear = 0;

    trips[start] = 0;
    queue[rear++] = start;

    while (front != rear) {
        int u = queue[front++];
        for (int v = 0; v < n; ++v) {
            if (graph[u][v] > 0 && trips[v] > trips[u] + 1) {
                trips[v] = trips[u] + 1;
                queue[rear++] = v;
            }
        }
    }

    if (trips[end] == INT_MAX) {
        return -1; // Если нет пути из города A в город B
    }

    // Рассчитываем минимальное количество поездок для доставки x тонн продукции
    int requiredTrips = (totalWeight + MAX_WEIGHT - 1) / MAX_WEIGHT; // Округляем вверх
    return trips[end] * requiredTrips;
}

int main() {
    int n;
    printf("Введите количество городов: ");
    scanf("%d", &n);

    int graph[MAXN][MAXN];
    printf("Введите матрицу смежности (или весов) для графа:\n");
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &graph[i][j]);
        }
    }

    int start, end, totalWeight;
    printf("Введите начальный город (A): ");
    scanf("%d", &start);
    printf("Введите конечный город (B): ");
    scanf("%d", &end);
    printf("Введите количество тонн продукции: ");
    scanf("%d", &totalWeight);

    int result = minTrips(n, graph, start, end, totalWeight);

    if (result == -1) {
        printf("Невозможно доставить продукцию из города %d в город %d\n", start, end);
    } else {
        printf("Минимальное количество поездок: %d\n", result);
    }

    return 0;
}

[BDA]

Если верно понял код, то у вас в массиве trips будет минимальное количество городов по дороге от А до Б, а нужно найти самую широкую дорогу от А до Б (Задача о самом широком пути).

[leksi223]

Не очень понял, извините. Необходимо переписать массив?

[BDA]

Вот граф городов по этой матрице смежности. Вы едете из "a" в "e". В "trips[4]" у вас число 3, т.е. нужно проехать по 3 ребрам графа (по 3 дорогам), чтобы попасть из города "a" в "e". Но нужно найти не минимальное количество ребер на пути, а такой путь, чтобы разрешенная масса груза на ней была максимальна. В данном случае есть два пути из "a" в "e": a-b-c-e, a-b-d-e, но на обоих максимальная масса груза ограничена 10. Поэтому понадобится 4 поездки, чтобы перевезти 40 тонн.

[leksi223]

Спасибо Огромное!!!