Fox Mulder s'est replongé dans les dossiers Warren. Pas (que) pour le plaisir, mais un indicateur lui a recommandé de s'intéresser à certaines enquêtes du plus célèbre couple d'enquêteurs du paranormal. Et en effet, Mulder a remarqué des détails un peu particuliers dans la façon dont Ed Warren classait ses dossiers. Premièrement, dans ses archives, chacun des cas semble posséder un indicateur numérique qui semble révéler la « puissance » du phénomène (en tout cas tel que ressenti par Lorraine Warren). D'autre part, Ed a laissé des écrits faisant des liens entre les différentes enquêtes, mais l'agent du FBI ne parvient pas à trouver les points communs qui ont conduit Ed à faire ces rapprochements, et le sens semble unidirectionnel.
Mulder a fini par représenter ces éléments par un système de graphe, dans lequel chaque nœud est un dossier qui porte la puissance évaluée par Lorraine, les nœuds étant reliés entre eux suivant les indications d'Ed. Et voilà que l'indicateur des Affaires Non Classées recommande à Mulder de s'intéresser à certains de ces dossiers en particulier, en précisant qu'ils sont liés entre eux mais en ne donnant qu'une suite de « puissances » évaluées par Lorraine.
Il aurait bien voulu l'aide de Scully, mais cette dernière est occupée sur une autopsie, et Mulder est parfaitement au courant de son dédain des thèses des Warrens, qu'elle qualifie de charlatans. Vous êtes donc l'espoir de Mulder pour résoudre cette énigme.
Les données d'entrée décrivent un graphe de plusieurs centaines de dossiers (la carrière des Warren s'étale sur plusieurs dizaines d'années), ainsi que la séquence de puissances fournie par l'indicateur. Pour en comprendre la description, voici l'entrée qui correspondrait à un petit graphe de 5 dossiers et une séquence de seulement 3 puissances :
Nombre de noeuds :
5
Puissances :
100, 105, 105, 90, 100
Voisins :
000 : 3,4
001 : 2
002 : 3
003 : 0
004 : 1,2
Sequence :
100, 105, 90
La première indication donne le nombre de dossiers (ici 5). Chaque dossier est ensuite numéroté de 0 à 4. La première énumération donne la puissance de chaque dossier (le dossier 0 a une puissance de 100, le dossier 3 de 90...). La seconde énumération indique quels dossiers sont atteignables depuis chaque dossier (depuis le dossier 0, on peut atteindre les dossiers 3 et 4...).
Ce qui précède décrit donc un graphe à 5 dossiers (5 nœuds), orienté, chaque nœud étant étiqueté par une puissance :
Étant donné un chemin sur ce graphe (qui passe de nœud en nœud en empruntant
les arcs orientés), par exemple, dossier 4 → dossier 2 → dossier 3, il est
facile de relever les puissances des 3 nœuds visités : 100, 105, 90.
Le problème inverse est plus difficile. Étant donnée une séquence de
puissances, comme 100, 105, 90, on cherche à retrouver le chemin qui a été
parcouru dans le graphe, c'est à dire la liste des nœuds visités, dans
l'ordre de leur visite.
Dans le cas du petit exemple, la séquence étant 100, 105, 90, il n'y a qu'un
seul chemin qui correspond (ce qui n'est pas a priori toujours le cas), et
c'est : 4, 2, 3. Le chemin 0, 2, 3 ne convient pas, il passe par les bonnes
puissances, mais on ne peut pas passer du sommet 0 au sommet 2, car il n'y a
pas d'arc 0→2. Le chemin 4, 1, 2 est un chemin valide (avec les bons arcs),
mais sa séquence de puissance est 100, 105, 105 et non 100, 105, 90.
Validez le défi en donnant la séquence des dossiers correspondant à la
séquence de puissance fournie dans ce format : 4, 2, 3.
