Un problème classique de théorie des graphes consiste à déterminer le chemin optimal entre deux points, en minimisant la distance totale et, à distance égale, le coût associé. Ce problème est modélisé à l'aide d'un graphe pondéré non orienté où les arêtes représentent des routes avec une longueur et un tarif péage.

Description du problème

Étant donné une carte de voyage avec N villes (numérotées de 0 à N-1) et M autoroutes, chaque autoroute reliant deux villes a une longueur et un péage. L'objectif est de trouver le chemin le plus court entre une ville source S et une destination D. Si plusieurs chemins ont la même longueur minimale, on sélectionne celui avec le péage total le plus bas.

Format d'entrée

L'entrée commence par une ligne contenant quatre entiers positifs N, M, S, D. N représente le nombre de villes (2 ≤ N ≤ 500), M le nombre d'autoroutes, S la source et D la destination. Les M lignes suivantes décrivent chaque autoroute : ville1, ville2, longueur, péage, séparés par des espaces. Tous les entiers sont ≤ 500. Une solution est garantie d'exister.

Format de sortie

Afficher sur une seule ligne la longueur du chemin et le péage total, séparés par un espace, sans espace en fin de ligne.

Exemple d'entrée

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

Exemple de sortie

3 40

Analyse de la solution

Ce problème se résout par l'algorithme de Dijkstra, qui calcule le plus court chemin dans un graphe à poids positifs. Ici, les poids sont la longueur des arêtes. Comme on doit aussi considérer le péage en cas d'égalité de distance, on maintient deux tableaux : un pour la distance minimale depuis la source, et un autre pour le coût correspondant. Lors de la mise à jour, si une distance égale est trouvée, on compare les coûts pour choisir le moins cher.

Implémentation en langage C

L'implémentation utilise une matrice d'adjacence pour stocker le graphe, avec des structures pour les arêtes et les données d'arête. L'algorithme de Dijkstra est adapté pour gérer les deux critères d'optimisation.

#include <stdio.h>
#include <stdlib.h>

#define MAX_SOMMETS 500
#define INFINI 1000000

typedef struct {
    int longueur;
    int cout;
} DonneesArete;

typedef struct {
    int nombreSommets;
    int nombreAretes;
    DonneesArete matrice[MAX_SOMMETS][MAX_SOMMETS];
} Graphe;

Graphe creerGraphe(int nbSommets) {
    Graphe g;
    g.nombreSommets = nbSommets;
    g.nombreAretes = 0;
    for (int i = 0; i < nbSommets; i++) {
        for (int j = 0; j < nbSommets; j++) {
            if (i == j) {
                g.matrice[i][j].longueur = 0;
                g.matrice[i][j].cout = 0;
            } else {
                g.matrice[i][j].longueur = INFINI;
                g.matrice[i][j].cout = INFINI;
            }
        }
    }
    return g;
}

void insererArete(Graphe *g, int v1, int v2, int longueur, int cout) {
    g->matrice[v1][v2].longueur = longueur;
    g->matrice[v1][v2].cout = cout;
    g->matrice[v2][v1].longueur = longueur;
    g->matrice[v2][v1].cout = cout;
}

void dijkstraOptimise(Graphe g, int source, int *distances, int *couts) {
    int marque[MAX_SOMMETS] = {0};

    for (int i = 0; i < g.nombreSommets; i++) {
        distances[i] = g.matrice[source][i].longueur;
        couts[i] = g.matrice[source][i].cout;
    }
    marque[source] = 1;

    for (int compteur = 0; compteur < g.nombreSommets - 1; compteur++) {
        int minDist = INFINI;
        int u = -1;
        for (int i = 0; i < g.nombreSommets; i++) {
            if (!marque[i] && distances[i] < minDist) {
                minDist = distances[i];
                u = i;
            }
        }
        if (u == -1) break;
        marque[u] = 1;

        for (int v = 0; v < g.nombreSommets; v++) {
            if (!marque[v] && g.matrice[u][v].longueur != INFINI) {
                int nouvelleDist = distances[u] + g.matrice[u][v].longueur;
                int nouveauCout = couts[u] + g.matrice[u][v].cout;
                if (nouvelleDist < distances[v]) {
                    distances[v] = nouvelleDist;
                    couts[v] = nouveauCout;
                } else if (nouvelleDist == distances[v] && nouveauCout < couts[v]) {
                    couts[v] = nouveauCout;
                }
            }
        }
    }
}

int main() {
    int N, M, S, D;
    scanf("%d %d %d %d", &N, &M, &S, &D);

    Graphe g = creerGraphe(N);
    for (int i = 0; i < M; i++) {
        int v1, v2, longueur, cout;
        scanf("%d %d %d %d", &v1, &v2, &longueur, &cout);
        insererArete(&g, v1, v2, longueur, cout);
    }

    int distances[MAX_SOMMETS];
    int couts[MAX_SOMMETS];
    dijkstraOptimise(g, S, distances, couts);

    printf("%d %d", distances[D], couts[D]);
    return 0;
}

Cette implémentation initialise les distances et coûts à partir de la source, puis itère pour sélectionner le sommet non marqué avec la plus petite distance. Les mises à jour prennent en compte la priorité par distance et, en cas d'égalité, par coût. Le résultat final affiche la distance et le coût miniamux pour la destination.