site de rencontre

Une entreprise, qui opère un site web de rencontres, a conclu des ententes avec des cafés. Lorsque deux membres du site désirent se rencontrer en personne, pour prendre un verre ou un dessert, le site de rencontres leur suggère le café «le plus près». Le café «le plus près» est le café qui permet aux deux membres de se rencontrer le plus proche possible. Il s'agit du café qui minimise la distance de déplacement du membre le plus éloigné (en mètres). Les cafés versent des ristournes à l'entreprise selon le nombre de membres référés. Vous devez écrire un programme C++, pour déterminer le café de rencontre le plus près pour deux personnes désirant se rencontrer en personne. À titre d'exemple, voici ci-dessous la carte d'une région fictive. Le poids des arêtes indique la distance séparant deux nœuds. Sur la carte, il y a 3 cafés partenaires situés aux sommets b, c et h.