Tournée de livraison la plus courte

Un coursier part de la ville 0, visite chaque autre ville exactement une fois puis revient à la ville 0. distances[i][j] représente le coût pour aller de i à j. Avec au plus 15 villes, une programmation dynamique avec masques de bits (Held–Karp) sur les ensembles visités est suffisamment rapide.

Implémentez shortest_tour(distances).

Entrée

distances : une matrice n × n des coûts de trajet ; distances[i][i] = 0.

Sortie

Retournez le coût du circuit le moins cher.

Contraintes

1 ≤ n ≤ 15 ; 0 ≤ coût ≤ 1 000 000

Exemples

Entrée :
distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

Sortie attendue :
expected = 80

Entrée :
std::vector<std::vector<long long>> distances = {
    {0, 10, 15, 20},
    {10, 0, 35, 25},
    {15, 35, 0, 30},
    {20, 25, 30, 0}
};

Sortie attendue :
long long expected = 80;

Entrée :
long[][] distances = new long[][] {
    new long[] {0, 10, 15, 20},
    new long[] {10, 0, 35, 25},
    new long[] {15, 35, 0, 30},
    new long[] {20, 25, 30, 0}
};

Sortie attendue :
long expected = 80;

Entrée :
distances = [
    [0]
]

Sortie attendue :
expected = 0

Entrée :
std::vector<std::vector<long long>> distances = {
    {0}
};

Sortie attendue :
long long expected = 0;

Entrée :
long[][] distances = new long[][] {
    new long[] {0}
};

Sortie attendue :
long expected = 0;

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

• Wikipedia: Held–Karp algorithm