DF 2008, Reconnaissance vocale

Bonjour!

J'ai résolu le problème Reconnaissance vocale de 2008, mais ma solution ne donne pas la bonne réponse au test 6. Je trouve 2 alors que la réponse est 9. Pourtant, je ne vois vraiment pas ce qui peut foirer dans mon programme, il est pas long et assez intuitif... J'ai essayé une autre interprétation du problème (par exemple si plusieurs chemins arrivent au même sommet, considérer que la probabilité du sommet est la somme de toutes les probabilités et chercher celui avec la plus grande, plutot que de chercher le chemin maximum, mais ca ne marche alors plus dans un test précédent).
J'ai regardé les données du test 6 (certes d'une manière pas très légale) parce que ca me perturbait, mais j'ai toujours pas d'idée concernant mon éventuelle erreur...
Est-ce que quelqu'un a le même problème que moi, ou une idée?

Oups, il s'agit du test 7, désolé.
Oups, il y avait un bouton pour modifier le message en fait, désolé :D

"J'ai résolu le problème Reconnaissance vocale de 2008" : non.
Sinon, pour t'aider, et bien je vais faire une demande classique: décris-nous l'algorithme, et/ou montre nous ton code via un site comme pastebin/ideone avec un délai d'expiration pas trop élevé.

Edit: J'ai essayé de le résoudre, et j'ai le même problème \^\^.
Après avoir triché moi aussi pour voir l'input, j'ai une question: que faire des arcs identiques sauf pour la valeur de probabilité? (je suppose que ça ne change rien en fait... chaque arc est un chemin différent)

Voilà : http://pastebin.com/Fr3AJv6W
Je procède lettre par lettre. Dans la variable combien[i][j], il y a la longueur du plus court chemin reliant le sommet initial au sommet i, et ayant pour étiquettes les j premières lettres de la chaine de caractère. La valeur est -1 s'il n'existe aucun tel chemin.
J'ai juste regardé j modulo 2 afin de gagner de la mémoire, mais ce n'était pas nécessaire (et je ne pense pas que le problème vienne de là).
Par exemple combien[initial][0] vaut 0 et tous les autres combien[i][0] valent -1. Ensuite, je calcule les combien[i][1] à partir des combien[i'][0] et des arcs i'->i qui ont la bonne étiquette, et ainsi de suite...

Pour moi aussi, chaque arc doit être considéré comme différent... J'y ai pensé aussi mais j'ai un peu la flemme de changer mon code pour faire la somme de ces arcs, et ca me parait un peu tordu en plus.

"il y a la longueur du plus court chemin" Comment ça? Plus court chemin en nombre d'étapes, c'est évident: j. Si par contre tu parles en somme de valeur, alors c'est plutôt "longueur du plus long chemin".
Je vais regarder ton code, même si je me sens un peu coupable de le faire avant d'avoir moi-même résolu ce problème...

Ah oui je parlais de la longueur du plus long chemin, désolé. C'est tellement inhabituel de chercher le plus long chemin :p
Et si tu en es arrivé au même stade que moi avec le même problème, on ne peut pas dire que tu voles mon code :D

On a la même solution, sauf que la mienne est encore plus moche, vu que je crée un vector temporaire puis je le recopie pour chaque étape de la boucle principale. On a plus qu'à réfléchir ou attendre une aide extérieure :)

Bon je pense qu'on va devoir se contenter de se dire qu'il y a une erreur dans ce test :)
Merci pour ton aide en tout cas!