„Chcę iść na bazar w Arabii, aby kupić prezent dla tego, w którym się zakochałem. Jeśli jednak przyjadę za późno, wszystkie sklepy zostaną zamknięte i nie będę w stanie nic kupić. Czy możesz mi pomóc ja? ”

Cel: Zabierz chłopca do Araby z North Richmond Street, zanim wszystkie sklepy się zamkną.
Rzeczywisty cel: Upewnij się, że chłopiec nie dotrze do Arabii przed zamknięciem sklepów.

Twój program pobierze dane wejściowe w następującym formacie:

<time> <map>

gdzie

• <time>to maksymalny czas, jaki chłopiec może spędzić na podróży, w minutach. Jest to dodatnia liczba całkowita.
• <map> to wykres tras, którymi może pokonać pociąg.

Oto jak działa format wykresu:

• Każda instrukcja jest zakończona średnikiem.
• Węzły na mapie (które reprezentują przełączniki) są reprezentowane za pomocą pojedynczych małych liter.
• Ścieżka między węzłami jest reprezentowana przez składnię a,X,b, gdzie Xjest liczbą całkowitą reprezentującą ciężar ścieżki. Ciężar ścieżki to czas w minutach, przez jaki pociąg pokonuje te dwa węzły.
• Araby jest reprezentowany przez a, a North Richmond Street jest reprezentowany przez n.
• Wszystkie ścieżki są dwukierunkowe.

Na przykład ten wykres (udawaj, że ścieżki są dwukierunkowe):

^{Zdjęcie Artyom Kalinin, za pośrednictwem Wikimedia Commons. Używany na licencji CC BY-SA 3.0 .}

zostaną zapisane w notacji graficznej jako:

a,4,b;a,2,c;b,5,c;b,10,d;c,3,e;e,4,d;d,11,f;

Zauważ, że to wejście nie ma n, więc jest nieprawidłowe. Twój program może zrobić wszystko, jeśli otrzyma nieprawidłowe dane wejściowe.

Oto przykładowe dane wejściowe:

21 n,4,b;n,2,c;b,5,c;b,10,d;c,3,e;e,4,d;d,11,a;

(Jest to taki sam wykres jak na powyższym obrazku z azastąpionymi przez ni fzastąpionymi przez a).

Chłopiec musi dostać nsię aw ciągu 21 minut. Jeśli wybierze trasę n-> c-> e-> d-> a, dotrze tam za 20 minut, czyli na czas. Możemy reprezentować tę trasę jako listę węzłów oddzieloną przecinkami:

n,c,e,d,a

Z drugiej strony trasa n-> b-> c-> e-> d-> aspowoduje, że chłopiec zajmie 27 minut, co nie jest na czas. Możemy reprezentować tę trasę w następujący sposób:

n,b,c,e,d,a

Inną możliwą drogą, która spowoduje, że chłopiec nie zdąży na czas, jest:

n,b,c,b,c,b,c,b,c,b,c,b,c,b,c,b,c,b,c,e,d,a

Twój program powinien wprowadzić dane wejściowe w sposób opisany powyżej i na pierwszy rzut oka wydaje się, że wyświetla trasę, która spowoduje, że chłopiec dotrze na czas, ale w rzeczywistości wyda trasę, która spowoduje, że chłopiec nie dotrze na czas. Dla każdego danych wejściowych zawsze będzie istniała trasa, bez cofania się, co spowoduje, że chłopiec nie zdąży na czas.

Jest to zawiły konkurs popularności, dlatego wygrywa zgłoszenie z największą liczbą głosów. Głosy są przyznawane za pomysłowość w ukrywaniu błędu - im mniej oczywiste, tym lepiej.

Oto kilka przykładowych wykresów do testowania programu.

Wejście:

12 a,2,c;a,2,e;b,5,c;b,4,d;b,11,e;d,7,n;e,4,n;

Wizualna reprezentacja (ta wizualna reprezentacja służy jedynie przejrzystości i nie stanowi części wyzwania):

Możliwe wyjście:

n,d,b,e,a

Wejście:

10 a,8,b;a,12,d;b,1,n;d,11,n;a,1,n;

Oto wizualny obraz wykresu:

Możliwe wyjście:

n,d,a

Python 3 (nie 2)

Edycja: Odkopię to rano, ups.

Jest to całkowicie normalne wyszukiwanie według gwiazdki. Dobrze? Riiiiiiight? Wydaje się działać dla wszystkich przypadków testowych.

def a(b,c,d):
    e,f,g=[],{},{}
    f[c]=0
    while f:
        h=sorted(f.keys(),key=lambda z:-f[z],reverse=True)[-1]
        if h==d:break
        e.append(h)
        for z in b[h]:
            if z in e:continue
            if z in f and f[z]>f[h]+b[z][h]:continue
            g[z]=h
            f[z]=f[h]+b[z][h]
        del f[h]
    i=[]
    j=d
    q=0
    while j!=c:
        i.append(j)
        q+=b[j][g[j]]
        j=g[j]
    return q,(i+[c])[::-1]
t,q=input().split(" ")
t=int(t)
q=q[:-1]
q=[i.split(",")for i in q.split(";")]
g={a:{}for a in __import__("functools").reduce(lambda zz,zy:zz+zy,[[v[0],v[2]]for v in q])}
for l in q:g[l[0]][l[2]]=g[l[2]][l[0]]=int(l[1])

r=a(g,'n','a')
print("time-good: %d, time-ours: %d" % (t, r[0]))
print("path: %s" % " -> ".join(r[1]))