Metro (Həll təhlili)

Mənbədən xət $l$-ə aid olan $v$ zirvəsinə olan ən qısa məsafəni dist[v][l] deyə saxlayırıq, burada 1 \le v \le 70, 1 \le l \le 10. Qraf qonşuluq siyahıları şəklində təmsil olunur. Hər bir istiqamət və qiymətə əlavə, hər bir kənar üçün oxşar olaraq, kənarın aparılacağı zirvənin aid olduğu metro xəttinin nömrəsi saxlanılır.

Alqoritm $line1$ xətti üzərində yerləşən $s$ stansiyasından başlanır. Axtarılan dəyər, $line2$ xətti üzərində yerləşən $f$ stansiyasına getmək üçün minimal yol qiymətidir.

Zirvələr arasında keçid edərkən eyni xəttə mənsub olub olmadığını yoxlamaq lazımdır: əgər xətlər fərqlidirsə, qiymətə $1$ əlavə olunur (xətlərin dəyişdirilməsi).

Dijkstra alqoritmi vasitəsilə (s, line1) vəziyyətindən (f, line2) vəziyyətinə qədər olan ən qısa məsafəni tapırıq.

Misal

Verilən misalda $1$ xəttində olan $2$ stansiyasından $3$ xəttində olan $7$ stansiyasına ən qısa marşrutu tapmaq tələb olunur.

• $1$ xətti ilə $2$ stansiyasından $1$ stansiyasına keçirik: $2$ dəqiqə.

• $1$ stansiyasında $1$ xəttindən $2$ xəttinə keçirik: $1$ dəqiqə.

• $2$ xətti ilə $1$ stansiyasından $5$ stansiyasına gedirik: $4$ dəqiqə.

• $5$ stansiyasında $2$ xəttindən $3$ xəttinə keçirik: $1$ dəqiqə.

• $3$ xətti ilə $5$ stansiyasından $7$ stansiyasına gedirik: $2$ dəqiqə.

Nəticədə bütün yol $10$ dəqiqə davam edir.

Alqoritmin reallaşdırılması

Qrafda olan zirvələrin sayı MAX = 71 qədərdir. Xəttlərin sayı LINES = 11 qədərdir.

#define MAX 71
#define LINES 11

Mənbədən xət $l$-ə aid olan $v$ zirvəsinə olan ən qısa məsafəni dist[v][l] deyə saxlayırıq. Ən qısa məsafələri saxlayan arrayi bəyan edək.

int dist[MAX][LINES];

node strukturu kənar haqqında məlumatı saxlayır:

• $to$ — kənarın istiqaməti;

• $cost$ — kənarın qiyməti;

• $line$ — kənarın aid olduğu metro xətti;

struct node
{
  int to, cost, line;
  node(int to, int cost, int line) : to(to), cost(cost), line(line) {}
};

node strukturu prioritetlərə dair növbədə də istifadə olunur, burada

• $to$ — cari zirvə;

• $cost$ — $to$ zirvəsinə (xətt $line$ üzərində) qədər olan minimal yol qiyməti;

• $line$ — $to$ zirvəsinin yerləşdiyi metro xəttinin nömrəsi;

Prioritetlərə dair növbədə zirvələr, yol qiyməti ilə yüksələn sırayla sıralanır.

bool operator< (node a, node b)
{
  return a.cost > b.cost;
}

Qrafı təmsil etmək üçün qonşuluq siyahısını bəyan edək.

vector<vector<node> > g;

Programın əsas səhifəsi. Giriş məlumatlarını oxuyuruq.

scanf("%d %d", &n, &l);
g.resize(n + 1);

$i$-ci metro xəttini oxuyuruq. Qonşu stansiyalar arasında olan hərəkət vaxtı $u$ və $v$ stansiyaları arasında $2$-yə bərabərdir.

for (i = 1; i <= l; i++)
{

$i$-ci metro xəttinin ilk stansiyası olan $u$ stansiyasını oxuyuruq. $u$ stansiyasından sonra $v$ gəlir.

  scanf("%d ", &u);
  while (scanf("%d%c", &v, &ch))
  {

Stansiyalar arasında hərəkət iki istiqamətdən mümkündür, bu halda kənarın qiyməti $2$-dir.

    g[u].push_back(node(v, 2, i));
    g[v].push_back(node(u, 2, i));
    u = v;

Sətirin sonuna çatdığımızda cari metro xəttinin məlumatlarının oxunuşu başa çatır.

    if (ch == '\n') break;
  }
}

Ən qısa məsafələri saxlayan arrayi ilkinləşdiririk.

for (i = 1; i <= n; i++)
for (j = 1; j <= l; j++)
  dist[i][j] = 2000000000;

Başlanğıc və son nöqtə stansiyalarının məlumatlarını oxuyuruq. Hər bir stansiyanın ona aid olan xətti verilir.

scanf("%d %d %d %d", &s, &line1, &f, &line2);

$line1$ xətti üzərində olan $s$ stansiyasından başlanırıq.

dist[s][line1] = 0;

$line1$ xətti üzərində olan $s$ başlanğıc zirvəsini saxlayan node strukturu növbəyə daxil edirik. Başlanğıc zirvəsinə çatmanın qiyməti $0$-dır.

priority_queue<node, vector<node> > pq;
pq.push(node(s, 0, line1)); // (v, cost, line)
while (!pq.empty())
{

Ən aşağı qiymətli zirvəni $v$ növbədən çıxarırıq.

  int cost = pq.top().cost;
  int v = pq.top().to;
  int l1 = pq.top().line;
  pq.pop(); // dist[v][l1] = cost

$v$ ilə qonşu olan bütün zirvələri sınaqdan keçiririk.

  for (auto edge: g[v])
  {

v \to to kənarını $w$ qiyməti ilə və $l2$ xəttinə aid olduğunu nəzərə alırıq.

    int to = edge.to;
    int w = edge.cost;
    int l2 = edge.line;

v \to to kənarı üzrə hərəkət edilərsə, yolun qiyməti cost + w olacaq.

    int tot_cost = cost + w;

$v$ və $to$ zirvələri ayrı xətlərə aid oldursa, $l1$ xəttindən $l2$ xəttinə keçmək lazımdır.

    if (l1 != l2) tot_cost += 1;

Əgər v \to to kənarı üzrə hərəkət cari dəyəri yaxşılaşdırırsa, dist[to][l2]-i yeniləyirik və zirvəni növbəyə daxil edirik (onun çatma qiyməti $tot\_cost$ və $l2$ xəttində yerləşir).

    if (tot_cost < dist[to][l2])
    {
      dist[to][l2] = tot_cost;
      pq.push(node(to, tot_cost, l2));
    }
  }
}

Cavabı — $line2$ xəttində olan $f$ zirvəyə ən qısa yolun qiymətini çap edirik.

printf("%d\n", dist[f][line2]);