Distribution automatique – Épreuve régionale 2018

Énoncé¶

Fort de ses succès dans la vente de crêpes, Joseph Marchand se lance dans une aventure encore plus audacieuse : produire en masse des crêpes qui seront distribuées en temps réel à des clients répartis sur toute une ville, en étant acheminées par des câbles aériens. (Un tel système a d'ailleurs été utilisé précédemment par l'organisation de Prologin pour distribuer des copies aux candidats, cf. le sujet écrit « Distributions tempérées » posé en 2014.)

Les crêpes sont produites dans la super-cuisine de Joseph, numérotée 0, et des distributeurs numérotés de 1 à n−1 permettent aux citadins de se servir en crêpes. Étant donnés deux distributeurs différents, ou la cuisine et un distributeur, on connaît le coût d'installation d'un câble entre les deux. On souhaite donc construire un réseau en installant des câbles, pour que tout distributeur soit atteignable par une crêpe sortie toute chaude de la cuisine en empruntant un ou plusieurs câbles successivement, tout en minimisant le coût total des câbles.

Au départ, Joseph Marchand ne s'occupait que de sa spécialité, à savoir la production de crêpes ; un réseau de distribution, qui était le moins cher possible, était fourni par un autre prestataire. Suite à un différend, ce dernier est parti et a démantelé son réseau. Joseph se retrouve donc à devoir construire lui-même un réseau de distribution, mais il n'a pas le droit de réutiliser le tracé optimal (en termes de coût), sous peine de violer la propriété intellectuelle du prestataire précédent.

Aidez Joseph Marchand à trouver le deuxième tracé le moins cher pour un réseau de distribution.

Si vous avez fini cet exercice, voici un autre défi : comment trouver le tracé le moins cher sous la contrainte qu'au plus K câbles partent directement de la cuisine ? Contactez un orga pour lui proposer une solution à l'oral.

Entrée¶

L'entrée comprendra :

• sur la première ligne, un entier naturel n ;
• sur les n lignes suivantes, une matrice carrée symétrique n×n d'entiers naturels, avec des zéros sur la diagonale, dont la case en i-ème ligne et j-ème colonne indique le coût de relier les points (cuisine ou distributeur) numérotés i et j par un câble direct.

Sortie¶

Vous afficherez en sortie le coût total du deuxième réseau le moins cher à construire.

Contraintes¶

• 1 ≤ n ≤ 800
• Les coûts des câbles seront compris entre 0 et 2 000 000.