TAN Network – CodinGame solution in Java
Read the stops into a map from id to index, convert latitudes and longitudes from degrees to radians, and weight each directed route with the statement's equirectangular distance. Run Dijkstra from the start stop, rebuild the path with predecessor links and print the stop names in order, or IMPOSSIBLE if the destination is never reached.
The problem
You get a start stop and a destination from the Nantes public transport network (TAN), followed by the list of stops and the list of direct routes between them. Each stop line is comma-separated: an identifier, a quoted full name, a description, a latitude and a longitude in degrees, and a few fields you can ignore.
Routes are one-way pairs of stop identifiers. The length of a route is given by a flat-Earth approximation: x = Δlongitude · cos(mean latitude), y = Δlatitude, distance = √(x² + y²) · 6371, with angles in radians. Print the names of the stops on the shortest route, one per line, or IMPOSSIBLE when there is none.
Approach, step by step
- Parse the stops carefullySplit each line on commas, map the identifier to an array index, strip the quotes from the name, and convert latitude and longitude to radians right away so the distance code cannot forget it.
- Build a directed graphEach route line 'A B' adds an edge from A to B only. Use the id-to-index map so that adding thousands of routes is O(1) each instead of a linear search.
- Weight edges with the given formulaUse the mean of both latitudes in the cosine, exactly as specified. Rounding or simplifying the formula can change which of two near-equal routes is shorter.
- Run DijkstraAll weights are positive, so Dijkstra with a priority queue is correct. Skip stale queue entries and stop early when the destination is popped.
- Rebuild and print the pathFollow predecessor links from the destination back to the start, then print the names in forward order. If the start equals the destination, print that single name; if the destination was never reached, print IMPOSSIBLE.
Complexity
O((N + M) log N)O(N + M)With a binary heap, each of the N stops is settled once and each of the M routes relaxed once. The original code's array scan for the closest stop and linear getStop() lookups make it O(N² + M·N), still fast enough for the test sizes.
Solution code
Bug fixed in this version: In the Java block, distance() computes cos((A.lat() + A.lat()) / 2) instead of cos((A.lat() + B.lat()) / 2), so every route length is slightly off and close alternatives can be ranked wrongly. It also uses new Double(String), which is deprecated for removal in recent Java versions. The replacement fixes both and replaces the O(N) stop lookup with a HashMap.
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);
}
}
Common mistakes
- Forgetting to convert to radiansThe coordinates are in degrees but Math.cos and the 6371 km radius expect radians. With degrees, distances are wrong by a large factor and the cosine term is nonsense, so routes are compared incorrectly on the validators.
- Treating routes as undirectedSome routes exist only in one direction. Adding the reverse edge creates shortcuts that do not exist and produces paths the validator rejects.
- Using BFS instead of DijkstraBFS minimises the number of stops, not the distance. The two often agree on small examples and then differ on the larger tests.
- Start equals destinationWhen both identifiers are the same, the expected output is just that stop's name. Path reconstruction loops written as 'while (cur != start)' handle it, but some early-exit code prints nothing.
- Losing empty fields when splittingUse split(",", -1) to keep empty fields so the latitude and longitude stay at positions 3 and 4 even when the description column is empty.
Going further
A* is a natural upgrade here because the coordinates give you a free heuristic: the straight-line distance from a stop to the destination, computed with the same formula, never overestimates the route length, since every route is itself a straight segment measured with that formula and the triangle inequality holds. Plug it in as priority = dist + h(stop) and the search stops expanding stops that point away from the destination. One caveat: the equirectangular formula is not a true metric on the sphere because the cosine uses the mean latitude of each pair, so in theory h can be very slightly inconsistent; in a city-sized network that error is tiny compared with the gaps between real alternatives, so in practice A* returns the same path as Dijkstra.
FAQ
Is the input in degrees or radians?
Degrees. Convert both latitude and longitude to radians before using them in the distance formula.
Why does my code pass the tests but fail validation?
The usual causes are degrees left unconverted, routes treated as two-way, or BFS used instead of Dijkstra; the larger validators expose all three.
Is O(N²) Dijkstra fast enough?
Yes for this puzzle's network size, but a priority queue version is just as short to write and scales far better.