Помогите найти ошибку кода!!! Срочно! Пожалуйста помогите!

Question

Помогите найти ошибку кода!!! Срочно! Пожалуйста помогите!

liza bolieva Ученик (112), на голосовании 5 месяцев назад

Условия задачи: Имеются n городов. Некоторые из них соединены двусторонними дорогами, причем для каждой дороги известна максимальная масса груза, который можно по ней везти одним транспортным средством. Напишите программу для определения минимального числа поездок, которое придется совершить из города А в город В, чтобы доставить х тонн продукции при условии, что предприниматель использует только одну фуру грузоподъемностью 20 тонн. При входных данных: Введите количество городов: 5
Введите матрицу смежности (или весов) для графа:
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
Введите начальный город (A): 0
Введите конечный город (B): 4
Введите количество тонн продукции: 40 Из города 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;
}```

Answer 1

Ошибка в коде заключается в том, что он не учитывает грузоподъемность на каждом участке пути. Алгоритм BFS находит кратчайший путь по количеству дорог, но не учитывает, что на некоторых участках дороги может быть ограничение по грузоподъемности, требующее дополнительных поездок.
Вот как исправить код:
#include <limits.h>

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

// Функция для поиска минимального числа поездок с учетом грузоподъемности
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 && graph[u][v] >= MAX_WEIGHT) {
// Рассчитываем количество поездок на данном участке
int requiredTripsForEdge = (totalWeight + graph[u][v] - 1) / graph[u][v];
// Обновляем количество поездок, если найден более короткий путь
if (trips[v] > trips[u] + requiredTripsForEdge) {
trips[v] = trips[u] + requiredTripsForEdge;
queue[rear++] = v;
}
}
}
}

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

int main() {
// ... (остальная часть кода остается без изменений)
}
В этом исправленном коде внутри цикла BFS мы рассчитываем количество поездок, необходимых для преодоления каждого участка пути (requiredTripsForEdge), учитывая грузоподъемность дороги (graph[u][v]). Затем мы обновляем общее количество поездок (trips[v]), если найден более короткий путь.
С этим изменением алгоритм будет учитывать грузоподъемность на каждом участке пути, и результат будет более точным.