Problème A : Voyage Éco-responsable

Ce problème nous demande de trouver le chemin le moins coûteux en émissions de carbone entre un point de départ et un point d'arrivée, tout en respectant une contrainte de distance maximale. Nous disposons de diverses options de transport avec leurs coûts d'émission par kilomètre.

Approche Nous pouvons modéliser ce problème comme une variante de l'algorithme de Dijkstra. Étant donné que nous avons deux critères à optimiser (émissions de CO2 minimales) et une contrainte (distance maximale), nous étendons l'état habituel d'un nœud dans Dijkstra. Au lieu de simplement stocker le coût minimal pour atteindre un nœud, nous stockons le coût minimal pour atteindre un nœud i après avoir parcouru une distance d.

Ainsi, notre état dans l'algorithme de Dijkstra devient un couple (sommet, distance_parcourue). Le coût associé à cet état est l'émission de CO2 minimale pour l'atteindre. Cette technique est connue sous le nom de Dijkstra bi-dimensionnel ou 2D. Le problème se ramène à trouver le chemin de coût minimum sur un graphe où chaque "état" (sommet, distance_parcourue) est un nœud.

La file de priorité de Dijkstra triera les états d'abord par les émissions de CO2 minimales (priorité la plus haute pour les plus faibles), puis par la distance parcourue (priorité la plus haute pour les plus faibles en cas d'émissions égales). Une attention particulière doit être portée à la taille des distances et des émissions, qui peuvent nécessitre l'utilisation de types long long.

Implémentation Voici une implémentation de cette approche :

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <tuple>
#include <limits>
#include <cstring> // Pour memset

// Utilisation de long long pour toutes les valeurs de distance et de CO2
using long_long = long long;

const long_long INF = std::numeric_limits<long_long>::max();
const int MAX_NODES = 222; // Nombre maximum de lieux (incluant départ/arrivée)
const int MAX_DISTANCE = 2222; // Distance maximale B

// Structure pour représenter un point dans le plan
struct Coordinates {
    int x, y;
};

// Structure pour un état dans la file de priorité de Dijkstra
struct PathState {
    long_long current_co2;
    int current_node;
    int traveled_distance;

    // L'opérateur < est surchargé pour implémenter un min-heap.
    // La priorité est donnée à la plus faible émission de CO2,
    // puis à la plus faible distance parcourue.
    bool operator<(const PathState& other) const {
        if (current_co2 != other.current_co2) {
            return current_co2 > other.current_co2; // Plus petit CO2 = plus haute priorité
        }
        return traveled_distance > other.traveled_distance; // Plus petite distance = plus haute priorité
    }
};

// Adjacence list: {target_node, distance, co2_cost_per_km}
std::vector<std::tuple<int, int, int>> graph_adj[MAX_NODES];

// Matrice pour stocker les émissions minimales de CO2 pour chaque état (noeud, distance)
long_long min_co2_emissions[MAX_NODES][MAX_DISTANCE];
bool visited_state[MAX_NODES][MAX_DISTANCE];

// Coordonnées de tous les lieux (0: départ, n+1: arrivée, 1..n: intermédiaires)
Coordinates node_positions[MAX_NODES];

// Coût d'émission par kilomètre pour chaque type de transport
long_long carbon_costs[MAX_NODES]; // C[0] pour le type par défaut

// Calcule la distance euclidienne arrondie à l'entier supérieur
int calculate_distance(Coordinates p1, Coordinates p2) {
    long_long dx = p1.x - p2.x;
    long_long dy = p1.y - p2.y;
    return static_cast<int>(std::ceil(std::sqrt(static_cast<double>(dx * dx + dy * dy))));
}

void run_dijkstra(int start_node, int max_travel_distance, int end_node) {
    // Initialisation de la matrice des coûts d'émission
    for (int i = 0; i < MAX_NODES; ++i) {
        for (int j = 0; j < MAX_DISTANCE; ++j) {
            min_co2_emissions[i][j] = INF;
            visited_state[i][j] = false;
        }
    }

    std::priority_queue<PathState> pq;

    min_co2_emissions[start_node][0] = 0;
    pq.push({0, start_node, 0}); // {co2, node, distance}

    while (!pq.empty()) {
        PathState current_state = pq.top();
        pq.pop();

        int u = current_state.current_node;
        int dist_u = current_state.traveled_distance;
        long_long co2_u = current_state.current_co2;

        if (visited_state[u][dist_u]) {
            continue;
        }
        visited_state[u][dist_u] = true;

        for (const auto& edge : graph_adj[u]) {
            int v = std::get<0>(edge);
            int edge_dist = std::get<1>(edge);
            int co2_per_km_type_idx = std::get<2>(edge); // Index du type de transport

            int new_dist = dist_u + edge_dist;
            long_long new_co2 = co2_u + edge_dist * carbon_costs[co2_per_km_type_idx];

            // Vérifier la contrainte de distance maximale
            if (new_dist > max_travel_distance) {
                continue;
            }

            // Relaxation de l'arête
            if (new_co2 < min_co2_emissions[v][new_dist]) {
                min_co2_emissions[v][new_dist] = new_co2;
                pq.push({new_co2, v, new_dist});
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    Coordinates start_coord, end_coord;
    std::cin >> start_coord.x >> start_coord.y >> end_coord.x >> end_coord.y;

    int max_allowed_distance;
    std::cin >> max_allowed_distance >> carbon_costs[0]; // C[0] est le coût par défaut

    int num_transport_types;
    std::cin >> num_transport_types;
    for (int i = 1; i <= num_transport_types; ++i) {
        std::cin >> carbon_costs[i];
    }

    int num_intermediate_nodes;
    std::cin >> num_intermediate_nodes;

    // Assigner les positions
    node_positions[0] = start_coord; // Noeud de départ
    node_positions[num_intermediate_nodes + 1] = end_coord; // Noeud d'arrivée

    for (int i = 1; i <= num_intermediate_nodes; ++i) {
        int x, y, num_outgoing_paths;
        std::cin >> x >> y >> num_outgoing_paths;
        node_positions[i] = {x, y};
        for (int j = 0; j < num_outgoing_paths; ++j) {
            int connected_node_idx, transport_type_idx;
            std::cin >> connected_node_idx >> transport_type_idx;
            // Adjust index for 0-based to 1-based internal representation
            connected_node_idx++;
            int dist = calculate_distance(node_positions[i], node_positions[connected_node_idx]);
            graph_adj[i].emplace_back(connected_node_idx, dist, transport_type_idx);
            graph_adj[connected_node_idx].emplace_back(i, dist, transport_type_idx); // Bidirectionnel
        }
    }

    // Ajouter les arêtes entre le point de départ (0), d'arrivée (n+1) et les intermédiaires
    // Utilise le type de transport par défaut (C[0])
    for (int i = 1; i <= num_intermediate_nodes; ++i) {
        int dist_to_start = calculate_distance(node_positions[i], node_positions[0]);
        graph_adj[i].emplace_back(0, dist_to_start, 0);
        graph_adj[0].emplace_back(i, dist_to_start, 0);

        int dist_to_end = calculate_distance(node_positions[i], node_positions[num_intermediate_nodes + 1]);
        graph_adj[i].emplace_back(num_intermediate_nodes + 1, dist_to_end, 0);
        graph_adj[num_intermediate_nodes + 1].emplace_back(i, dist_to_end, 0);
    }
    
    // Ajouter l'arête directe entre le départ et l'arrivée
    int direct_dist = calculate_distance(node_positions[0], node_positions[num_intermediate_nodes + 1]);
    graph_adj[0].emplace_back(num_intermediate_nodes + 1, direct_dist, 0);
    graph_adj[num_intermediate_nodes + 1].emplace_back(0, direct_dist, 0);


    run_dijkstra(0, max_allowed_distance, num_intermediate_nodes + 1);

    long_long min_total_co2 = INF;
    for (int d = 0; d <= max_allowed_distance; ++d) {
        min_total_co2 = std::min(min_total_co2, min_co2_emissions[num_intermediate_nodes + 1][d]);
    }

    if (min_total_co2 == INF) {
        std::cout << "-1" << std::endl;
    } else {
        std::cout << min_total_co2 << std::endl;
    }

    return 0;
}

Problème F : Icebergs

Ce problème nous demande de calculer la somme des aires d'un ensemble de polygones.

Approche La méthode la plus courante et efficace pour calculer l'aire d'un polygone est la formule du lacet (ou "shoelace formula"), qui est basée sur la triangulation du polygone. Cette formule utilise les coordonnées des sommets du polygone. Pour un polygone avec des sommets \((x_0, y_0), (x_1, y_1), \dots, (x_{n-1}, y_{n-1})\) listés dans l'ordre (horaire ou anti-horaire), l'aire est donnée par :

\( \text{Aire} = \frac{1}{2} \left| \sum_{i=0}^{n-1} (x_i y_{i+1} - x_{i+1} y_i) \right| \)

où \((x_n, y_n) = (x_0, y_0)\). Alternativement, on peut décomposer le polygone en triangles ayant un sommet commun (par exemple, le premier sommet \((x_0, y_0)\)). L'aire du polygone est alors la somme des aires signées de ces triangles. L'aire signée d'un triangle \((P_1, P_2, P_3)\) peut être calculée en utilisant le produit vectoriel (ou produit mixte 2D) de deux de ses côtés représentés comme des vecteurs. Par exemple, pour les vecteurs \((P_2 - P_1)\) et \((P_3 - P_1)\), le produit vectoriel est \((x_2-x_1)(y_3-y_1) - (x_3-x_1)(y_2-y_1)\). Cette valeur représente deux fois l'aire signée du triangle. Il faut prendre la valeur absolue de la somme finale et la diviser par 2.

Implémentation L'implémentation suivante utilise la méthode de triangulation via le produit vectoriel :

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm> // Pour std::abs

// Utilisation de long long pour les calculs d'aire afin d'éviter les débordements
using long_long = long long;

// Structure pour représenter un point 2D
struct Point2D {
    long_long x, y;
};

// Calcule le produit vectoriel de deux vecteurs (p1, p2) et (p1, p3)
// Ceci est égal à 2 * l'aire signée du triangle formé par P1, P2, P3
long_long cross_product(Point2D p1, Point2D p2, Point2D p3) {
    Point2D vec1 = {p2.x - p1.x, p2.y - p1.y};
    Point2D vec2 = {p3.x - p1.x, p3.y - p1.y};
    return vec1.x * vec2.y - vec1.y * vec2.x;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_polygons;
    std::cin >> num_polygons;

    long_long total_area_sum = 0;

    while (num_polygons--) {
        int num_vertices;
        std::cin >> num_vertices;

        std::vector<Point2D> vertices(num_vertices);
        for (int i = 0; i < num_vertices; ++i) {
            std::cin >> vertices[i].x >> vertices[i].y;
        }

        long_long current_polygon_signed_area_double = 0;
        // Triangulation depuis le premier sommet
        for (int i = 1; i < num_vertices - 1; ++i) {
            current_polygon_signed_area_double += cross_product(vertices[0], vertices[i], vertices[i+1]);
        }
        
        // L'aire est la moitié de la valeur absolue de la somme
        total_area_sum += std::abs(current_polygon_signed_area_double);
    }

    // Chaque appel à cross_product donne 2 * l'aire, donc la somme finale est 2 * l'aire totale.
    // Il faut diviser par 2 à la fin.
    std::cout << total_area_sum / 2 << std::endl;

    return 0;
}

Problème K : Observation des Oiseaux

Ce problème porte sur l'identification de nœuds dans un graphe orienté. Nous cherchons tous les nœuds u pour lesquels toute trajectoire partant de u et atteignant un nœud cible s doit obligatoirement emprunter l'arête directe (u, s). En d'autres termes, l'arête (u, s) est un pont essentiel pour toute communication entre u et s.

Approche Pour résoudre ce problème, nous utilisons une approche basée sur le graphe inversé (où toutes les arêtes sont inversées) et un parcours en largeur (BFS) spécialisé. L'idée est la suivante : si u est un tel nœud, alors dans le graphe inversé, toutes les chemins de s à u doivent passer par l'arête (s, u) (l'arête inversée de (u, s)). Si u est atteignable depuis s par une autre voie dans le graphe inversé (c'est-à-dire sans utiliser l'arête (s, u)), alors u n'est pas une solution.

L'algorithme procède comme suit :

1. Construire le graphe inversé où chaque arête (x, y) de l'original devient (y, x).
2. Identifier tous les nœuds candidats u qui ont une arête directe (u, s) vers la cible s dans le graphe original. Ces nœuds sont stockés dans une liste.
3. Pour chaque nœud u candidat, exécuter un parcours en largeur (BFS) sur le graphe inversé. Ce BFS démarre de u et explore tous les nœuds v qui sont atteignables depuis u sans passer par le nœud cible s ni par u lui-même (pour éviter les boucles triviales ou les chemins indésirables).
4. Pendant ces BFS, nous maintenons deux tableaux pour suivre l'état :

• path_counts_from_candidates[v] : Compte combien de fois le nœud v a été "atteint" par un BFS lancé depuis un nœud candidat différent (ou par son propre BFS initial), sans passer par s.
• bfs_originator[v] : Enregistre quel nœud candidat a initié le BFS qui a découvert v pour la première fois. Ceci est crucial pour gérer les cycles et éviter de compter plusieurs fois les chemins d'un même BFS.

5. Après avoir exécuté tous les BFS pour tous les nœuds candidats, nous examinons path_counts_from_candidates[u] pour chaque u candidat. Si path_counts_from_candidates[u] est égal à 1, cela signifie que u n'a été affecté que par son propre BFS (l'incrémentation initiale de son compteur). Autrement dit, aucun autre nœud candidat j n'a pu atteindre u dans le graphe inversé (sans passer par s). Cela implique que la seule façon pour u d'attiendre s dans le graphe original est par l'arête (u, s). Ces nœuds u sont nos solutions.

Implémentation

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm> // Pour std::sort

const int MAX_NODES = 100000 + 10; // Maximum N + 10

// Liste d'adjacence pour le graphe inversé
std::vector<int> adj_reverse[MAX_NODES];

int num_nodes, num_edges, target_node_s;

// Liste des nœuds u qui ont une arête directe (u, s) vers la cible
std::vector<int> critical_candidates;

// Compte le nombre de chemins "non-s" vers un nœud depuis des candidats différents
int path_counts_from_candidates[MAX_NODES];

// Marque quel candidat a initié le BFS qui a découvert ce nœud
int bfs_originator[MAX_NODES];

// Fonction BFS spécialisée pour chaque candidat
void special_bfs(int current_candidate_u) {
    path_counts_from_candidates[current_candidate_u]++; // Le candidat se compte lui-même

    std::queue<int> q;
    q.push(current_candidate_u);
    bfs_originator[current_candidate_u] = current_candidate_u; // Marque u comme origine de son propre BFS

    while (!q.empty()) {
        int current_node = q.front();
        q.pop();

        for (int neighbor_v : adj_reverse[current_node]) {
            // Si le voisin est la cible 's', ou le candidat de départ 'u' lui-même,
            // ou si son path_count est déjà > 1 (signifiant déjà couvert par un autre chemin/candidat),
            // on n'explore pas davantage par cette voie.
            if (neighbor_v == target_node_s || neighbor_v == current_candidate_u || path_counts_from_candidates[neighbor_v] > 1) {
                continue;
            }

            // Si le voisin n'a pas encore été visité par ce BFS
            if (bfs_originator[neighbor_v] != current_candidate_u) {
                bfs_originator[neighbor_v] = current_candidate_u; // Marque V comme visité par ce BFS
                q.push(neighbor_v);
                path_counts_from_candidates[neighbor_v] += path_counts_from_candidates[current_node]; // Accumule les "comptes de chemins"
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_nodes >> num_edges >> target_node_s;

    // Construction du graphe inversé et identification des candidats
    for (int i = 0; i < num_edges; ++i) {
        int u_origin, v_destination;
        std::cin >> u_origin >> v_destination;
        if (v_destination == target_node_s) {
            critical_candidates.push_back(u_origin); // u_origin est un candidat si (u_origin, s) est une arête
        }
        adj_reverse[v_destination].push_back(u_origin); // Ajouter l'arête (v_destination, u_origin) au graphe inversé
    }

    // Lancer le BFS spécialisé pour chaque candidat
    for (int candidate_u : critical_candidates) {
        special_bfs(candidate_u);
    }

    // Filtrer les candidats valides
    std::vector<int> final_solutions;
    for (int candidate_u : critical_candidates) {
        if (path_counts_from_candidates[candidate_u] == 1) {
            final_solutions.push_back(candidate_u);
        }
    }

    std::sort(final_solutions.begin(), final_solutions.end());

    std::cout << final_solutions.size() << std::endl;
    for (int u_solution : final_solutions) {
        std::cout << u_solution << std::endl;
    }

    return 0;
}