Marşrutlaşdırma (Bürünc)#11185

Marşrutlaşdırma (Bürünc) (Həll təhlili)

Hər marşrut şəhərlərin istiqamətləndirilmiş ardıcıllığını təyin edir. Bessi yalnız bir marşrutdan istifadə etmək istədiyi üçün, hər marşrut üçün yalnız aşağıdakını yoxlamaq kifayətdir:

$A$ şəhəri $B$ şəhərindən əvvəl rast gəlinirmi?

Əgər bu şərt yerinə yetirilirsə, Bessi həmin marşrutdan istifadə edə bilər və onun sabit dəyərini ödəyə bilər. Bütün uyğun marşrutlar arasında minimal dəyərə malik marşrutu tapmaq lazımdır.

Misal

Misalda $3$ marşrut var:

$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 və $B = 2$ B = 2 olduğundan, Bessi yalnız üçüncü marşrutdan istifadə edə bilər: bu marşrutda $1$ şəhəri $2$ şəhərindən əvvəl rast gəlinir. Bu marşrutun dəyəri $8$ -ə bərabərdir.

Alqoritmin realizasiyası

$I N F$ sabitini elan edirik.

#define INF 1000000000

Giriş məlumatlarını oxuyuruq.

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

Cavabı saxlayacağımız $r es$ dəyişənini işə salırıq.

res = INF;

$n$ marşrutu araşdırırıq.

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

Marşrutun dəyəri $cos t$ və bu marşrutdakı şəhərlərin sayı $sz$ -i oxuyuruq.

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

$f l a g$ dəyişəni, əgər $А$ şəhəri hazırkı marşrutda hələ rast gəlinməyibsə, $f a l se$ dəyərini saxlayır.

  flag = false;

Hazırkı marşrutdakı şəhərləri ardıcıl olaraq oxuyuruq.

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

Əgər $А$ şəhəri rast gəlinərsə, $f l a g = t r u e$ flag = true təyin edirik.

    if (city == a) flag = true;

Əgər $B$ şəhəri rast gəlinərsə və bundan əvvəl marşrutda artıq $А$ şəhəri rast gəlinibsə $(f l a g = t r u e)$ (flag = true), onda Bessi bu marşrutdan istifadə edə bilər, onun $cos t$ dəyərini ödəyərək.

Əgər uyğun marşrutlar bir neçədirsə, minimal dəyərə malik marşrutu seçirik.

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

Bütün marşrutlar emal edildikdən sonra cavabı çıxarırıq.

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