Prologin
2025
Énoncé¶
La finale Prologin 2018 approche rapidement, et comme chaque année, un ravitaillement constant en crêpes est nécessaire à la survie des candidats. L'entreprise de Joseph Marchand a été choisie afin de maintenir ce flux de livraison de crêpes faites maison, et Joseph veut anticiper l'ampleur de la logistique derrière la finale afin d'organiser aux mieux ses différents magasins entre eux.
L'idée est que si un magasin arrive à court d'ingrédients, des camions se chargeraient de transporter ceux manquant depuis d'autres magasins. C'est la première fois que l'entreprise de Joseph Marchand est chargée de la finale Prologin, et leur service logistique est totalement perdu ! En effet, Joseph veut anticiper différents scénarios de crise d'ingrédients, et la logistique peine à calculer les kilomètres parcourus par les camions.
En tant que nouveau responsable algorithmicien de l'entreprise, vous venez à la rescousse. Actuellement, Joseph voudrait connaître la somme totale des plus courts chemins reliant chacun de ses magasins, afin d'anticiper une possible apocalypse des crêpes. Heureusement, le service logistique a récemment numérisé toutes les informations concernant les routes entre les magasins et vous transmet ces données sous la forme d'un graphe où chaque nœud est un magasin, et chaque route un arc.
On définit un plus court chemin entre deux nœuds comme étant un ensemble d'arcs reliant ces deux nœuds de telle sorte que la somme des poids des arcs soit minimale. Cela signifie que la route directe entre deux magasins n'est pas nécessairement le plus court chemin, car il peut être plus intéressant dans certains cas de passer par un magasin intermédiaire.
Entrée¶
La première ligne contient deux entiers $N$ et $M$ correspondant respectivement aux nombres de magasins et aux nombres de routes.
$M$ lignes suivent contenant 3 entiers et décrivant chacune une route entre un magasin $u$ et un magasin $v$ d'une distance totale de $w$. Les routes peuvent être parcourues dans les deux sens.
Sortie¶
Un entier indiquant la somme totale des plus courts chemins entre chacun des magasins. Il est garanti que la réponse tient dans un entier signé de 32 bit.
Contraintes¶
- $1 \le N \le 20$
- $1 \le M \le \displaystyle\frac{N\cdot (N - 1)}{2}$
- $1 \le u, v \le N$
- $1 \le w \le 100$
Contraintes de performance¶
- $1 \le N \le 10000$
- $1 \le M \le \min\left (1000, \displaystyle\frac{N\cdot (N - 1)}{2}\right)$
