Énoncé du problème

Une agence de voyage dans la ville d'Adelton sur l'île de Zanzibar souhaite proposer des circuits touristiques. Pour maximiser ses profits, elle a décidé de trouver le plus court circuit qui commence et se termine au même endroit. Écrivez un programme qui détermine un tel circuit.

La ville comprend N intersections numérotées de 1 à N et M routes bidirectionnelles numérotées de 1 à M. Plusieurs routes peuvent relier deux mêmes intersections, mais une route ne relie jamais une intersection à elle‑même. Chaque circuit touristique est une séquence d'identifiants de routes y₁, …, yₖ (k > 2). La route yᵢ (1 ≤ i ≤ k‑1) relie les intersections xᵢ et xᵢ₊₁, et la route yₖ relie xₖ et x₁. Tous les x₁, …, xₖ doivent être distincts. La longueur du circuit est la somme des longueurs des routes qui le composent.

Le programme doit soit trouver un circuit de longueur minimale, soit afficher qu'aucun circuit n'existe.

Entrée / Sortie

• Entrée : première ligne : N ≤ 100, M ≤ 10 000. Chacune des M lignes suivantes : trois entiers positifs (le numéro de la première intersection, le second, et la longueur de la route, strictement inférieure à 500).
• Sortie : soit la chaîne "No solution." s'il n'y a aucun circuit, soit les numéros des intersections du plus court circuit dans l'ordre de parcours (séparés par des espaces). En cas d'ex æquo, une seule solution peut être fournie.

Exemple

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

Sortie : 1 3 5 2

Solution

Le problème consiste à trouver le cycle de poids minimal dans un graphe non orienté. Une approche naïve par recherche en profondeur serait trop lente (N ≤ 100). On utilise l'algorithme de Floyd‑Warshall pour détecter les cycles courts.

L'idée est d'examiner chaque triplet (k, j, i) avec j < i < k. Pour un k donné, on considère le chemin de j à i via des sommets strictement inférieurs à k (c'est-à-dire la « plus courte » distance stockée dans la matrice dist avant la mise à jour par k). Ensuite on ajoute les arêtes (j, k) et (k, i) pour former un cycle. Avant que k ne soit utilisé comme sommet intermédiaire, dist[j][i] représente le plus court chemin de j à i utilisant seulement des sommets < k. C'est donc le « second plus court » chemin potentiel, et la somme avec les deux arêtes directes donne un cycle candidat. On garde le minimum.

Pour reconstruire le cycle, on maintient une matrice pred[u][v] qui stocke le prédécesseur de v sur le plus court chemin de u à v (dans l'état courant de Floyd). Lorsque l'on met à jour dist[j][i] via k, on met aussi à jour pred[j][i] = pred[k][i].

Si aucun cycle n'est trouvé, la réponse est "No solution." Sinon on affiche la séquence des sommets du cycle.

Implémentation en C (adaptée)

#include <stdio.h>
#include <string.h>

int graph[105][105];   // matrice des arêtes (INF si non connecté)
int dist[105][105];    // distances actuelles pour Floyd
int predecessor[105][105];
int cycle[105], lenCycle;
int found = 0, best = 1e9;

int min(int a, int b) { return a < b ? a : b; }

void floyd_cycle(int n) {
    for (int k = 1; k <= n; ++k) {
        // Vérifier les cycles passant par k
        for (int i = 1; i < k; ++i) {
            for (int j = i+1; j < k; ++j) {
                if (graph[i][k] == 1e9 || graph[k][j] == 1e9 || dist[i][j] == 1e9) continue;
                int candidate = dist[i][j] + graph[i][k] + graph[k][j];
                if (candidate < best) {
                    best = candidate;
                    found = 1;
                    // Reconstruire le cycle
                    lenCycle = 0;
                    int cur = j;
                    while (cur != i) {
                        cycle[++lenCycle] = cur;
                        cur = predecessor[i][cur];
                    }
                    cycle[++lenCycle] = i;
                    cycle[++lenCycle] = k;
                }
            }
        }
        // Mise à jour classique de Floyd
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dist[i][k] == 1e9 || dist[k][j] == 1e9) continue;
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    predecessor[i][j] = predecessor[k][j];
                }
            }
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    // Initialisation
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            graph[i][j] = (i == j) ? 0 : 1e9;
        }
    }
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        if (w < graph[u][v]) {
            graph[u][v] = graph[v][u] = w;
        }
    }
    // Copie dans dist et initialisation de predecessor
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            dist[i][j] = graph[i][j];
            if (graph[i][j] != 1e9 && i != j) {
                predecessor[i][j] = i;
            } else {
                predecessor[i][j] = -1;
            }
        }
    }

    floyd_cycle(n);

    if (!found) {
        printf("No solution.\n");
    } else {
        for (int i = 1; i <= lenCycle; ++i) {
            printf("%d ", cycle[i]);
        }
        printf("\n");
    }
    return 0;
}