Səyahət#2267

Səyahət (Həll təhlili)

İki qraf quracağıq: yollar qrafı $g [0]$ və cığırlar qrafı $g [1]$ . Sonra Domnino kəndindən $t$ bütün kəndlərə qədər olan ən qısa məsafələri hesablayacağıq:

Stefanın xəritəsi üzrə: $d [0] [i]$ — $t$ -dən $i$ kəndinə olan minimal məsafə;
Konstantinin xəritəsi üzrə: $d [1] [i]$ — $t$ -dən $i$ kəndinə olan minimal məsafə;

Sonra qraf baxaq ki, zirvələri cütlük $(v, p a r i t y)$ (v, parity) olan bir qrafdır:

$v$ — kəndin nömrəsi;
$p a r i t y = 0$ parity = 0 (gecə, yollarda hərəkət), $p a r i t y = 1$ parity = 1 (gün, cığırlarla hərəkət).

Ordu başlanğıc kəndindən gecə yola düşür, yol boyunca gecə hərəkət edir $(p a r i t y = 0)$ (parity = 0). Aşağıdakı qaydalara görə $(s, 0)$ zirvəsindən dərindən axtarışı başladırıq:

$(v, 0)$ (gecə) zirvəsindən $(u, 1)$ zirvəsinə yola gedirik, əgər $d [0] [u] < d [0] [v]$ d[0][u] < d[0][v];
$(v, 1)$ (gün) zirvəsindən $(u, 0)$ zirvəsinə cığırla gedirik, əgər $d [1] [u] < d [1] [v]$ d[1][u] < d[1][v].

$(v, p a r i t y)$ (v, parity) vəziyyətində əhəmiyyətli keçidləri nəzərdən keçiririk, yəni Domnino-ya olan məsafənin ciddi azaldığı keçidləri. Bunların arasında maksimum uzunluğu olan yolu axtarırıq.

Hər bir hetman öz xəritəsindəkini məsafəni azaltmağa çalışır (ən qısa yola getməyə məcbur deyil).

Dərindən axtarışı yerinə yetirəndə aşağıdakı dinamikliyi dəstəkləyəcəyik:

$d p [t y p e] [v]$ dp[type][v] — $v$ -dən $t$ -yə olan maksimum uzunluğu, başlanğıcdan $t y p e$ ilə.

Hər əhəmiyyətli keçid üçün:

$df s (t o, t y p e \oplus 1)$ dfs(to, type \oplus 1) rekursiv çağırırıq — qarşı fazaya keçid.
$d p [t y p e] [v]$ dp[type][v] dəyərini yeniləyirik:

d p [t y p e] [v] = ma x (d p [t y p e] [v], d p [t y p e \oplus 1] [t o] + w e i g h t);

dp[type][v] = max(dp[type][v], dp[type \oplus 1][to] + weight);

Beləliklə, ən yaxşı növbəti keçidi seçirik ki, ümumi maksimum yolu daha uzun olsun. Bu, DAG-a (yönəlik asiklik qraf) ən uzun yolu axtarışına bir analoqluqdur, burada kənarların istiqaməti ən qısa məsafənin azalmasına əsaslanır.

Cədvələ görə Domnino-ya olan məsafəni azaldan zirvələri yalnız hərəkət etmək icazəlidir. Lakin, məsələdə iki qraf var – iki növ kənar: yollar və cığırlar, – bu qədər növ keçidləri gecə (yol), gün (cığır), gecə, gün və s. ilə ardıcıl olur. Əslində bu ardıcıl xəritələrdən (yollar və cığırlar) zirvələrin arasında dövr yarana bilər, hətta hər bir tək qrafada (bir xəritədə) hərəkət həmişə azalma məsafə ilə olur.

Dərindən axtarış zamanı emal olunma stackində artıq olan bir zirvəni yenidən ziyarət edsək, dövrə daxil olduğumuzu göstərir.

Alqoritmin tələbi

Konstantları elan edək.

#define INF 2e18
#define MAXN 1005

İstifadə olunan məlumat strukturlarını elan edək:

$g [0]$ və $g [1]$ — yollar və cığırlar qrafları üçün sıralama listlər.
$d [0]$ və $d [1]$ — Domnino kəndindən $t$ bütün digər kəndlərə olan ən qısa məsafələr.
$d p [0]$ və $d p [1]$ — $v$ zirvəsindən $t$ -yə maksimum uzunluğu $v$ -dən yola başlasak $(t y p e = 0)$ (type = 0) veya cığırdan $(t y p e = 1)$ (type = 1).
$u se d [0]$ və $u se d [1]$ — yollar və cığırlar qraflarının dərin axtarış mərhələləri ilə işarələnmiş zirvələr.

vector<pair<int, int>> g[2][MAXN];
long long d[2][MAXN];
long long dp[2][MAXN];
int used[2][MAXN];

dijkstra funksiyası Domnino kəndindən $t$ bütün digər kəndləri ya yolla $(t y p e = 0)$ (type = 0) ya da cığırla $(t y p e = 1)$ (type = 1) ən kısa məsafələri hesablayır.

void dijkstra(int type)
{
  for (int i = 1; i <= n; i++)
    d[type][i] = INF;

  d[type][t] = 0;

  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  pq.push({ 0, t });

  while (!pq.empty())
  {
    pair<long long, int> top = pq.top();
    pq.pop();

    long long dist = top.first;
    int v = top.second;

    if (dist > d[type][v]) continue;

    for (auto edge : g[type][v])
    {
      int to = edge.first;
      int w = edge.second;

      if (d[type][to] > d[type][v] + w)
      {
        d[type][to] = d[type][v] + w;
        pq.push({ d[type][to], to });
      }
    }
  }
}

C++

dfs funksiyası dərindən axtarış aparır və alternativ kartlarla hərəkət edərək, $v$ kəndindən yola $(t y p e = 0)$ (type = 0) ya da cığırla $(t y p e = 0)$ (type = 0) ən uzun yolu tapır. Alternativ hərəkət zamanı dövr tapılabiləcək bir imkanda varsa funksiyanı $- 1$ qaytarır.

void dfs(int v, int type)
{

$v$ zirvəsi $g [t y p e]$ g[type] qrafında boz olur.

  used[type][v] = 1;

Dinamikliyi təşkili edirik.

  dp[type][v] = 0;

Zirvə $v$ -dən $g [t y p e]$ g[type] qrafında çıxan kənarları keçiririk.

  for (auto edge : g[type][v])
  {
    int to = edge.first;
    int weight = edge.second;

Zirvə $v$ -dən $t o$ zirvəsinə keçmək yalnız Domnino-ya $t o$ -dan olan məsafə $v$ -dən olan məsafədən az olduğu zaman mümkündür.

    if (d[type][to] < d[type][v])
    {

Əgər $g [t y p e \oplus 1]$ g[type \oplus 1] qrafında zirvə $t o$ artıq proses olunursa (boz edilibsə), bir dövr tapılıb – $- 1$ qaytarırıq.

      if (used[type ^ 1][to] == 1)
      {
        cout << -1 << endl;
        exit(0);
      }

Əgər $g [t y p e \oplus 1]$ g[type \oplus 1] qrafında zirvə $t o$ hələ ziyarət edilməyibsə, onu dərindən araşdırmağa davam edirik.

      if (used[type ^ 1][to] == 0)
        dfs(to, type ^ 1);

Bütün əhəmiyyətli keçidlərdən sonra dinamikliyi hərtərəfli yenidən hesablayırıq, $v$ zirvəsindən $g [t y p e]$ g[type] qrafında Domnino-ya qədər ən uzun yolu seçərək.

      dp[type][v] = max(dp[type][v], dp[type ^ 1][to] + weight);
    }
  }

$v$ zirvəsi $g [t y p e]$ g[type] qrafında qara olur.

  used[type][v] = 2;
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Yollar və cığırlar qraflarını qururuq.

scanf("%d %d %d", &n, &s, &t);
scanf("%d", &m1);
for (i = 0; i < m1; i++)
{
  scanf("%d %d %d", &a, &b, &len);
  g[0][a].push_back({ b, len });
  g[0][b].push_back({ a, len });
}

scanf("%d", &m2);
for (i = 0; i < m2; i++)
{
  scanf("%d %d %d", &a, &b, &len);
  g[1][a].push_back({ b, len });
  g[1][b].push_back({ a, len });
}

C++

Domnino kəndindən $t$ hər kəndə qədər ən qısa məsafəni ayrılıqda yollar və cığır xəritələri ilə hesablayırıq.

dijkstra(0);
dijkstra(1);

Dərindən axtarışdan istifadə edərək, yollarla hərəkət edərək alternativ kartlarla ən uzun yolu tapırıq, $s$ kəndindən yola başlayaraq.

dfs(s, 0);

Nəticəni çap edirik. Başlanğıc nöqtə — kənd $s$ , hərəkət yollarla başlanır.

printf("%lld\n", dp[0][s]);