,
Je ne sais pas si c'est connu en france, mais dans l universite ou je suis
tout les ans il y a un concours de intrenational de programmation l ACM, quelques pb sont donnes et on doit en resoudre le maximum en un certain temps.
 
http://www.acmcontest-pacnw.org/
 
Je ne m y suis pas inscrit, je ne m estime pas assez caid pour ca  .
 
voici un exercice propose par l'ACM International Collegiate Programming a Albert-Ludwigs University, Freiburg, Germany.
 
Erdos Numbers
The Hungarian Paul Erdos (1913–1996, pronounced as “Ar-dish”) was not only one of the strangest mathematicians of the 20th century, he was also among the most famous ones.
He kept on publishing widely circulated papers up to a very high age, and every mathematician having the honor of being a co-author to Erd¨os is well respected.
Not everybody got a chance to co-author a paper with Erd¨os, so many people were content if they managed to publish a paper with somebody who had published a paper with Erdos.
This gave rise to the so-called Erdos numbers. An author who has jointly published with Erdros had Erdros number 1.  
An author who had not published with Erdos but with somebody with Erdos number 1 obtained Erdos number 2, and so on.
Today, nearly everybody wants to know what Erdos number he or she has. Your task is to write a program that computes Erdos numbers for a given set of scientists.
 
Input
The input file contains a sequence of scenarios, each scenario consisting of a paper database and a list of names. A scenario begins with the line “p n”, where p and n are natural numbers with 1 <= p <= 32000; 1 <= n <= 3000.
Following this line are p lines containing descriptions of papers (this is the paper database).  
A paper is described by a line of the following form:
 
LastName1, FirstName1, LastName2, Firstname2, . . . : TitleOfThePaper
 
The names and the title may contain any ASCII characters between 32 and 126 except commas and colons.
There will always be exactly one space character following each comma. The first name may be abbreviated, but the same name will always be written in the same way.
In particular, Erdos’ name is always written as “Erdos, P.”.  
 
Example:
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors
matrices  
 
After the p papers follow n lines each containing exactly one name in the same format as in the paper
database.
The line ‘0 0’ terminates the input.
No name will consist of more than 40 characters. No line in the input file contains more than 250 characters.
In each scenario there will be at most 10 000 different authors.
Output For every scenario first print the number of the scenario in the format shown in the sample output.
Then print for every author name in the list of names their Erd¨os number based on the papers in the paper database of the scenario.
The authors should be output in the order given in the input file. Authors that do not have any relation to Erd¨os via the papers have Erdos number infinity.  
Adhere to the format shown in the sample output.
 
un exemple
Sample Input
4 3
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factor matrices  
Erdos, P., Reisig, W.: Stuttering in petri nets
Smith, M.N., Chen, X.: First oder derivates in structured programming
Jablonski, T., Hsueh, Z.: Selfstabilizing data structures
Smith, M.N.
Hsueh, Z.
Chen, X.
 
Sample Output
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2
 
 
si sa pose pb je peus le traduire en francais.
Je nai jamais eu a faire a ce genre de pb, j ai entendu dire qu il fallait utiliser un "graph", comme dans le genre dexercices : ( trouver el chemin le plus rapide entre les points A et B, A,B etant relier par different chemin et points) je ne suis pas sur des termes on parle de edge et vertice aussi ?
 
Pour commencer est ce que vous avait une idee sur la facon d extraire les noms en c++ ?
exemple : Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factor matrices  
je veus ajouter   Smith, M.N.    ,    Martin, G. .... a un vecteur.  
 
et plus generalement une idee sur la datastructure a utiliser ?
   

j ai regarde dans la stl y a pas de class graph ?
par contre boost en implement une, mais  j'y ai pas le droit

Ben tu pompes discrètement le code.

ça serait pas le plus court chemin dans un graphe où chaque arc vaut 1 par hasard ?
Genre calculer (la longueur de) le plus court chemin entre Erdos et tous les autres ?

oui c est ca.
mais pour extraire les noms ? separe les auteur de leur publication comment faire ?

table de hachage nom de l'auteur -> noeud dans le graphe.
 
edit : mais c'est bêtement Dijkstra ou j'ai raté une finesse ? Cet algo donne directement les distance d'un noeud à tous les autres et fait apparaître les infinis dans le foulée il me semble.

mais le nom de lauteur je le recupere comment ?

bah tu coupes sur la virgule et sur les deux points, bourrinement (en virant au passage le nom de la publi qui ne sert à rien). C'est un cas d'école, pas un problème de saisie robuste.

hum ok, mais comme j ai jamais fait vraiment d etraction de donne en c++ je savais pas trop, en java j utilise soit les tokens ou exp reg.  
 
donc la si je fais un  
while sting[i] != ',' copie dans un tempstring c est potable.
 
bon au boulot

j ai un drole de bug

le  getline(cin,paper); ne fait rien du tout la premier fois. il affiche direct le flag (-1)
par contre si je met deux getline a la suite c est bon.
j avais deja eu ce pb avant, (corriger par 2 getline mais cest surement pas la bonne mehtode).
un truc a faire avant ?

extraction des autheurs
jai dut rajouter un second getline a cause de pb plus haut
et string.find(n) ne renvoyant en grand entier si il ne trouve pas le n ja i fais un if line.find(",:" ) < line.lenght() a la place
 
sinon sa marche    

"Use breadth-first search instead of Dijkstra's algorithm when all edge weights are equal to one"
 
http://www.boost.org/libs/graph/do [...] paths.html