Перевезення корів (Бронза)#11185

Перевезення корів (Бронза) (Розбір)

Кожен маршрут задає напрямлену послідовність міст. Оскільки Бессі хоче скористатися лише одним маршрутом, для кожного маршруту достатньо перевірити:

чи зустрічається місто $A$ раніше за місто $B$ ?

Якщо ця умова виконується, Бессі може скористатися даним маршрутом і заплатити його фіксовану вартість. Серед усіх підходящих маршрутів необхідно знайти маршрут з мінімальною вартістю.

Приклад

У прикладі є $3$ маршрути:

$3 \to 2 \to 1$ 3 \to 2 \to 1;
$2 \to 1 \to 4 \to 3$ 2 \to 1 \to 4 \to 3;
$4 \to 1 \to 7 \to 8 \to 2$ 4 \to 1 \to 7 \to 8 \to 2;

Оскільки $A = 1$ A = 1, а $B = 2$ B = 2, Бессі може скористатися лише третім маршрутом: місто $1$ зустрічається в ньому раніше за місто $2$ . Вартість цього маршруту дорівнює $8$ .

Реалізація алгоритму

Оголосимо константу $I N F$ .

#define INF 1000000000

Читаємо вхідні дані.

scanf("%d %d %d", &a, &b, &n);

Ініціалізуємо змінну $r es$ , в якій будемо зберігати відповідь.

res = INF;

Перебираємо $n$ маршрутів.

for (i = 0; i < n; i++)
{

Читаємо вартість маршруту $cos t$ та кількість міст $sz$ на цьому маршруті.

  scanf("%d %d", &cost, &sz);

Змінна $f l a g$ містить $f a l se$ , якщо місто $А$ ще не зустрілося на поточному маршруті.

  flag = false;

Послідовно читаємо міста поточного маршруту.

  for (j = 0; j < sz; j++)
  {
    scanf("%d", &city);

Якщо зустрілося місто $А$ , встановлюємо $f l a g = t r u e$ flag = true.

    if (city == a) flag = true;

Якщо зустрілося місто $B$ , і до цього на маршруті вже зустрілося місто $А (f l a g = t r u e)$ А~(flag = true), то Бессі може скористатися цим маршрутом, заплативши його вартість $cos t$ .

Якщо підходящих маршрутів декілька, обираємо маршрут з мінімальною вартістю.

    if (flag && city == b) res = min(res, cost);
  }
}

Після обробки всіх маршрутів виводимо відповідь.

if (res == INF)
  printf("-1\n");
else
  printf("%d\n", res);