"Je veux aller au bazar d'Araby pour acheter un cadeau pour celui dont je suis tombé amoureux. Cependant, si j'arrive trop tard, tous les magasins seront fermés et je ne pourrai rien acheter. Pouvez-vous m'aider moi? "

Objectif: amener le garçon à Araby depuis North Richmond Street avant la fermeture de tous les magasins.
Objectif réel: s'assurer que le garçon n'arrive pas à Araby avant la fermeture des magasins.

Votre programme prendra en entrée dans le format suivant:

<time> <map>

où

• <time>est le temps maximum que le garçon peut passer à voyager, en minutes. C'est un entier positif.
• <map> est un graphique des itinéraires que le train peut emprunter.

Voici comment fonctionne le format du graphique:

• Chaque instruction se termine par un point-virgule.
• Les nœuds de la carte (qui représentent des commutateurs) sont représentés en utilisant des lettres minuscules simples.
• Un chemin entre les nœuds est représenté avec la syntaxe a,X,b, où Xest un entier représentant le poids du chemin. Le poids du chemin est le temps, en minutes, que prend le train pour passer par ces deux nœuds.
• Araby est représentée par a, et North Richmond Street est représentée par un n.
• Tous les chemins sont bidirectionnels.

Par exemple, ce graphique (faites comme si les chemins étaient bidirectionnels):

^{Image d'Artyom Kalinin, via Wikimedia Commons. Utilisé sous la licence CC BY-SA 3.0 .}

serait enregistré dans la notation graphique comme:

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

Notez que cette entrée n'a pas de n, c'est donc une entrée non valide. Votre programme peut faire n'importe quoi s'il reçoit une entrée non valide.

Voici un exemple d'entrée:

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

(C'est juste le même graphique que l'image ci-dessus avec aremplacé par net fremplacé par a).

Le garçon doit se nrendre adans les 21 minutes. S'il prend la route n-> c-> e-> d-> a, il y arrive en 20 minutes, ce qui est à temps. Nous pourrions représenter cette route comme une liste de nœuds séparés par des virgules:

n,c,e,d,a

D'un autre côté, l'itinéraire n-> b-> c-> e-> d-> afera prendre au garçon 27 minutes, ce qui n'est pas à temps. Nous pourrions représenter cette route comme ceci:

n,b,c,e,d,a

Un autre itinéraire possible qui empêchera le garçon d'arriver à temps est:

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

Votre programme doit accepter l'entrée comme décrit ci-dessus et, à première vue, semble produire un itinéraire qui amènera le garçon à arriver à temps, mais émet en fait un itinéraire qui empêche le garçon de le faire à temps. Pour toute entrée donnée, il existera toujours un itinéraire, sans retour en arrière, qui empêchera le garçon de se rendre à temps.

Il s'agit d'un concours de popularité sournois, donc l'entrée avec le plus de votes gagne. Des votes sont accordés pour l'ingéniosité à cacher le bug - moins c'est évident, mieux c'est.

Voici quelques exemples de graphiques pour tester votre programme.

Contribution:

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

Une représentation visuelle (cette représentation visuelle est uniquement à des fins de clarté et ne fait pas partie du défi):

Une sortie possible :

n,d,b,e,a

Contribution:

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

Voici une image visuelle du graphique:

Une sortie possible :

n,d,a

Python 3 (pas 2)

Edit: je débloquerai ceci le matin, oups.

C'est une recherche d'étoile A parfaitement normale. Droite? Riiiiiiight? Semble fonctionner pour tous les cas de test.

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]))