Donjons et Dragons – Épreuve régionale 2013

Énoncé¶

Vous êtes un valeureux chevalier dans un donjon où se trouve une princesse. Chacune des portes est gardée par un dragon qui vous fait perdre 100 PV (points de vie). On appelle sortie une salle comportant une unique porte. Sortir du donjon revient à rejoindre une sortie depuis la salle de départ (la salle 0).

Votre but n'est pas de sauver la princesse, non (vous ne savez même pas où elle est), mais de fuir ! Connaissant votre nombre de points de vie initial, vous est-il possible de rejoindre une sortie vivant ? On vous demande de retourner le nombre maximal de points de vie que vous pouvez avoir hors du donjon, -1 si vous êtes mort avant. Vous êtes morts si votre nombre de points descend à zéro ou moins.

Entrée¶

En entrée, on vous donne :

• Sur la première ligne, votre nombre de points de vie initiaux P
• Sur la deuxième ligne, deux entiers N et M correspondant respectivement au nombre de salles et au nombres de portes du donjon
• Sur les M prochaines lignes, un couple d'entier (a,b) représentant une porte entre les salles a et b.

Sortie¶

En sortie, vous devez renvoyer le nombre maximal de points de vie que vous pouvez avoir hors du donjon ou -1 si vous êtes mort avant.

Contraintes¶

• m <= 10 000
• n <= 10 000