Komplette Grafik mit nur zwei möglichen Kosten. Was kostet der kürzeste Weg von 0 bis N - 1?
Sie erhalten ein vollständiges ungerichtetes Diagramm mit N Eckpunkten. Alle außer K-Kanten kosten A. Diese K-Kanten kosten B, und Sie kennen sie (als Liste von Paaren). Was sind die Mindestkosten von Knoten 0 bis Knoten N - 1?
2 <= N <= 500k
0 <= K <= 500k
1 <= A, B <= 500k
Das Problem ist offensichtlich, wenn diese K Kanten mehr kosten als die anderen und Knoten 0 und Knoten N - 1 durch eine K-Kante verbunden sind.
Dijkstra funktioniert nicht. Ich habe sogar etwas sehr ähnliches mit einem BFS versucht.
Step1: Let G(0) be the set of "good" adjacent nodes with node 0.
Step2: For each node in G(0):
compute G(node)
if G(node) contains N - 1
return step
else
add node to some queue
repeat step2 and increment step
Das Problem ist, dass dies viel Zeit in Anspruch nimmt, da Sie für jeden Knoten eine Schleife von 0 nach N - 1 erstellen müssen, um die "guten" benachbarten Knoten zu finden.
Hat jemand bessere Ideen? Danke.
Bearbeiten: Hier ist ein Link vom ACM-Wettbewerb:http://acm.ro/prob/probleme/B.pdf