Il nous faut plus de crêpes ! – Épreuve régionale 2018

Niveau 5

É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)$

Contraintes d'exécution

Utilisation mémoire maximum
10000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
4 5
1 2 1
1 3 3
2 3 1
2 4 4
3 4 2
Exemple de sortie
26
Commentaire

Voici le graphe correspondant à l'entrée :

En partant du nœud 1, la somme des plus courts chemins vers les autres nœuds est de 1 + 2 + 4 = 7. En commençant au nœud 2, on a : 1 + 1 + 3 = 5. À partir du nœud 3 : 1 + 2 + 2 = 5. Et enfin, en partant du nœud 4 : 2 + 3 + 4 = 9. La somme totale est donc de 7 + 5 + 5 + 9 = 26.

Exemple d'entrée
9 10
9 6 2
2 3 4
4 3 2
7 6 2
1 2 2
8 9 3
3 5 1
2 4 3
6 8 1
1 5 3
Exemple de sortie
94
Commentaire

Du nœud 1 : 2 + 4 + 5 + 3 = 14
Du nœud 2 : 2 + 4 + 3 + 5 = 14
Du nœud 3 : 4 + 4 + 2 + 1 = 11
Du nœud 4 : 5 + 3 + 2 + 3 = 13
Du nœud 5 : 3 + 5 + 1 + 3 = 12

À noter que les nœuds 6, 7, 8, 9 n'interviennent jamais dans la somme des plus courts chemins des nœuds 1 à 5 car aucuns chemins n'existent entre ces différents magasins.

Du nœud 6 : 2 + 1 + 2 = 5
Du nœud 7 : 2 + 3 + 4 = 9
Du nœud 8 : 1 + 3 + 3 = 7
Du nœud 9 : 2 + 4 + 3 = 9