Пълна графика само с две възможни разходи. Каква е цената на най-краткия път от 0 до N - 1

Това е трудоемка работа по случай:

1. A ‹ B и 0 и N-1 се съединяват с A -> trivial.
2. B ‹ A и 0 и N-1 се съединяват с B -> trivial.
3. B ‹ A и 0 и N-1 се съединяват от A -> Do BFS на графика само с K ръбове.

4. A ‹ B и 0 и N-1 се съединяват от B -> Можете да проверите в O(N) време дали има път с дължина 2*A (опитайте всеки връх в средата).

   За да проверите други дължини на пътя, следният алгоритъм трябва да свърши работа: Нека X(d) е набор от възли, достижими чрез d по-къси ръбове от 0. Можете да намерите X(d), като използвате следния алгоритъм: Вземете всеки връх v с неизвестно разстояние и итеративно проверете ръбовете между v и върховете от X(d-1). Ако сте намерили къс ръб, тогава v е в X(d), в противен случай сте стъпили на дълъг ръб. Тъй като има най-много K дълги ръбове, можете да стъпите върху тях най-много K пъти. Така че трябва да намерите разстоянието на всеки връх за най-много O(N + K) време.

Предлагам решение на малко по-общ проблем, при който може да имате повече от два типа ръбове и теглата на ръбовете не са ограничени. За вашия сценарий идеята вероятно е малко пресилена, но изпълнението е доста просто, така че може да е добър начин да се справите с проблема.

Можете да използвате сегментно дърво, за да направите Dijkstra по-ефективен. Ще ви трябват операциите

• задаване на горна граница в диапазон, както е дадено U, L, R; за всички x[i] с L ‹= i ‹= R, задайте x[i] = min(x[i], u)
• намерете глобален минимум

Горните граници могат да бъдат лениво избутани надолу по дървото, така че и двете могат да бъдат внедрени в O(log n)

Когато отпускате изходящите ръбове, потърсете ръбовете с цена B, сортирайте ги и актуализирайте диапазоните между тях наведнъж.

Времето на изпълнение трябва да бъде O(n log n + m log m), ако сортирате всички ръбове отпред (по изходящ връх).

РЕДАКТИРАНЕ: Бях приет с този подход. Хубавото при него е, че избягва всякакъв вид специална обвивка. Все още има ~80 реда код.

В случай, когато A ‹ B, бих използвал нещо като BFS, където ще проверявате къде не можете да достигнете, вместо къде можете. Ето псевдокода:

G(k) is the set of nodes reachable by k cheap edges and no less. We start with G(0) = {v0}

while G(k) isn't empty and G(k) doesn't contain vN-1 and k*A < B
  A = array[N] of zeroes
  for every node n in G(k)
    for every expensive edge (n,m)
      A[m]++
  # now we have that A[m] == |G(k)| iff m can't be reached by a cheap edge from any of G(k)
  set G(k+1) to {m; A[m] < |G(k)|} except {n; n is in G(0),...G(k)}
  k++

По този начин избягвате итерация през (много) евтини ръбове и само итерация през сравнително малкото скъпи ръбове.

Както правилно отбелязахте, проблемът идва, когато A > B и край от 0 до n-1 има цена A.

В този случай можете просто да изтриете всички ръбове в графиката, които имат цена A. Това е така, защото оптималният маршрут трябва да има само ръбове с цена B.

След това можете да извършите проста BFS, тъй като разходите за всички ръбове са еднакви. Това ще ви осигури оптимална производителност, както е посочено от тази връзка: Намиране на най-краткия път за равно претеглена графика

Освен това можете да спрете своя BFS, когато общата цена надвиши A.