TAN Network – solution CodinGame en Java
On lit les arrêts dans une table identifiant vers indice, on convertit latitudes et longitudes des degrés en radians, et on pondère chaque liaison orientée avec la distance équirectangulaire de l'énoncé. On lance Dijkstra depuis l'arrêt de départ, on reconstruit le chemin grâce aux prédécesseurs et on affiche les noms des arrêts dans l'ordre, ou IMPOSSIBLE si la destination n'est jamais atteinte. Avec un tas binaire, le tout est en O((N + M) log N).
L'énoncé
On reçoit un arrêt de départ et une destination du réseau de transport nantais (TAN), puis la liste des arrêts et la liste des liaisons directes entre eux. Chaque ligne d'arrêt est séparée par des virgules : un identifiant, un nom complet entre guillemets, une description, une latitude et une longitude en degrés, et quelques champs à ignorer.
Les liaisons sont des paires orientées d'identifiants. La longueur d'une liaison suit une approximation de Terre plate : x = Δlongitude · cos(latitude moyenne), y = Δlatitude, distance = √(x² + y²) · 6371, avec des angles en radians. Il faut afficher les noms des arrêts du plus court trajet, un par ligne, ou IMPOSSIBLE s'il n'en existe aucun.
La démarche, étape par étape
- Analyser les arrêts avec soinOn découpe chaque ligne sur les virgules, on associe l'identifiant à un indice de tableau, on retire les guillemets du nom et on convertit tout de suite latitude et longitude en radians, pour que le code de distance ne puisse pas l'oublier.
- Construire un graphe orientéChaque ligne de liaison « A B » ajoute un arc de A vers B uniquement. On passe par la table identifiant vers indice pour que l'ajout de milliers de liaisons coûte O(1) chacune au lieu d'une recherche linéaire.
- Pondérer les arcs avec la formule donnéeOn utilise la moyenne des deux latitudes dans le cosinus, exactement comme spécifié. Arrondir ou simplifier la formule peut changer laquelle de deux liaisons presque égales est la plus courte.
- Lancer DijkstraTous les poids sont positifs, donc Dijkstra avec une file de priorité est correct. On ignore les entrées périmées de la file et on s'arrête dès que la destination est extraite.
- Reconstruire et afficher le cheminOn remonte les prédécesseurs depuis la destination jusqu'au départ, puis on affiche les noms dans le sens direct. Si le départ égale la destination, on affiche ce seul nom ; si la destination n'a jamais été atteinte, on affiche IMPOSSIBLE.
Complexité
O((N + M) log N)O(N + M)Avec un tas binaire, chacun des N arrêts est fixé une fois et chacune des M liaisons relâchée une fois. Le balayage de tableau du code d'origine pour trouver l'arrêt le plus proche et ses recherches linéaires dans getStop() le rendent O(N² + M·N), ce qui reste assez rapide pour les tailles des tests.
Code de la solution
TAN Network – Java
import java.util.*;
import java.io.*;
class Solution {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String start = br.readLine().trim();
String end = br.readLine().trim();
int n = Integer.parseInt(br.readLine().trim());
Map<String, Integer> index = new HashMap<>();
String[] names = new String[n];
double[] lat = new double[n], lon = new double[n];
for (int i = 0; i < n; i++) {
String[] f = br.readLine().split(",", -1);
index.put(f[0], i);
names[i] = f[1].replace("\"", "");
lat[i] = Math.toRadians(Double.parseDouble(f[3]));
lon[i] = Math.toRadians(Double.parseDouble(f[4]));
}
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int m = Integer.parseInt(br.readLine().trim());
for (int i = 0; i < m; i++) {
String[] r = br.readLine().trim().split(" ");
adj.get(index.get(r[0])).add(index.get(r[1]));
}
int s = index.get(start), t = index.get(end);
double[] dist = new double[n];
int[] prev = new int[n];
Arrays.fill(dist, Double.POSITIVE_INFINITY);
Arrays.fill(prev, -1);
dist[s] = 0;
// Dijkstra with a binary heap; entries are {distance, stop}
PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(a[0], b[0]));
pq.add(new double[]{0, s});
while (!pq.isEmpty()) {
double[] top = pq.poll();
int u = (int) top[1];
if (top[0] > dist[u]) continue; // stale entry
if (u == t) break;
for (int v : adj.get(u)) {
double x = (lon[v] - lon[u]) * Math.cos((lat[u] + lat[v]) / 2);
double y = lat[v] - lat[u];
double d = dist[u] + Math.sqrt(x * x + y * y) * 6371;
if (d < dist[v]) {
dist[v] = d;
prev[v] = u;
pq.add(new double[]{d, v});
}
}
}
if (dist[t] == Double.POSITIVE_INFINITY) {
System.out.println("IMPOSSIBLE");
return;
}
Deque<String> path = new ArrayDeque<>();
for (int v = t; v != -1; v = prev[v]) path.push(names[v]);
for (String name : path) System.out.println(name);
}
}
Erreurs fréquentes
- Oublier la conversion en radiansLes coordonnées sont en degrés mais Math.cos et le rayon de 6371 km attendent des radians. En degrés, les distances sont fausses d'un gros facteur et le terme en cosinus n'a aucun sens, donc les liaisons sont mal comparées sur les validateurs.
- Traiter les liaisons comme non orientéesCertaines liaisons n'existent que dans un sens. Ajouter l'arc inverse crée des raccourcis inexistants et produit des trajets que le validateur rejette.
- Utiliser un BFS au lieu de DijkstraLe BFS minimise le nombre d'arrêts, pas la distance. Les deux coïncident souvent sur les petits exemples puis divergent sur les plus gros tests.
- Départ égal à la destinationQuand les deux identifiants sont identiques, la sortie attendue est simplement le nom de cet arrêt. Les boucles de reconstruction écrites en « while (cur != start) » le gèrent, mais certains codes à sortie anticipée n'affichent rien.
- Perdre les champs vides au découpageUtilisez split(",", -1) pour conserver les champs vides, afin que latitude et longitude restent aux positions 3 et 4 même quand la colonne description est vide.
Pour aller plus loin
A* est une amélioration naturelle ici, car les coordonnées offrent une heuristique gratuite : la distance en ligne droite d'un arrêt à la destination, calculée avec la même formule, ne surestime jamais la longueur du trajet, puisque chaque liaison est elle-même un segment droit mesuré avec cette formule et que l'inégalité triangulaire tient. On la branche en priorité = dist + h(arrêt) et la recherche cesse d'étendre les arrêts qui s'éloignent de la destination. Une réserve : la formule équirectangulaire n'est pas une vraie métrique sur la sphère, car le cosinus utilise la latitude moyenne de chaque paire, donc en théorie h peut être très légèrement incohérente ; sur un réseau à l'échelle d'une ville, cette erreur est infime devant les écarts entre les vraies alternatives, et en pratique A* renvoie le même trajet que Dijkstra.
Questions fréquentes
L'entrée est-elle en degrés ou en radians ?
En degrés. Convertissez latitude et longitude en radians avant de les utiliser dans la formule de distance.
Pourquoi mon code passe les tests mais échoue à la validation ?
Les causes habituelles sont des degrés non convertis, des liaisons traitées à double sens, ou un BFS à la place de Dijkstra ; les validateurs plus gros révèlent les trois.
Un Dijkstra en O(N²) est-il assez rapide ?
Oui pour la taille du réseau de ce puzzle, mais une version à file de priorité est aussi courte à écrire et passe bien mieux à l'échelle.