Donjons et Dragons – Regional event 2013

Level 4

É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. 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 <= 10000
  • n <= 10000

Runtime constraints

Maximum memory usage
600 kilobytes
Maximum execution time
200 milliseconds

Input/output samples

Sample input
300
6 5
0 1
1 2
0 3
3 5
3 4
Sample output
100

Submit your solution

You have to register or log in to be able to submit your solution.