3.4 — задача из примера в теме 3.2.2 «All-Pairs Shortest Path»3.4 — a problem from the example in topic 3.2.2 "All-Pairs Shortest Path"
В 3.2.2 упоминалось: атлас или логистическая система с небольшим числом узлов может предвычислить полную матрицу расстояний один раз и отвечать на запросы за O(1). Здесь — конкретная сеть дорог между городами, для которой нужно построить такую таблицу и найти самый удалённый по расстоянию город от каждого.3.2.2 mentioned that an atlas or logistics system with a small number of nodes can precompute the full distance matrix once and answer queries in O(1). Here's a concrete road network between cities for which such a table must be built, and the farthest-by-distance city from each one must be found.
Дано n городов (пронумерованы 0..n-1), список рёбер `roads[i] = [a, b, dist]` — двусторонняя дорога между a и b длиной `dist`, и порог `threshold`. Нужно найти город, у которого наименьшее число других городов достижимо в пределах `threshold` (при равенстве — вернуть город с наибольшим номером). Это LeetCode-подобная формулировка ("Find the City With the Smallest Number of Neighbors at a Threshold Distance"), взятая как конкретный числовой пример на идею из 3.2.2.Given n cities (numbered 0..n-1), a list of edges `roads[i] = [a, b, dist]` — a bidirectional road between a and b of length `dist` — and a threshold. Find the city with the fewest other cities reachable within `threshold` (on a tie, return the city with the largest number). This is a LeetCode-style formulation ("Find the City With the Smallest Number of Neighbors at a Threshold Distance"), used here as a concrete numeric example of the idea from 3.2.2.
// Example
n = 4, threshold = 4
roads = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]]
// output: 3Здесь ровно та мотивация из 3.2.2: n мало (город из атласа, не миллион перекрёстков), а вопрос требует знать расстояние между КАЖДОЙ парой городов, а не только от одного источника — то есть это по определению задача All-Pairs Shortest Path, а не однократный запуск Дейкстры. Строим полную матрицу `dist[i][j]` по алгоритму 3.2.2: инициализируем dist[i][i]=0, dist[i][j]=длина дороги, если она есть напрямую, иначе INF, и трижды прогоняем тройной цикл k-i-j.This is exactly the motivation from 3.2.2: n is small (an atlas-sized city, not a million intersections), and the question requires knowing the distance between EVERY pair of cities, not just from one source — meaning by definition this is an All-Pairs Shortest Path problem, not a single Dijkstra run. We build the full `dist[i][j]` matrix per 3.2.2's algorithm: initialize dist[i][i]=0, dist[i][j]=the road's length if a direct one exists, otherwise INF, and run the triple k-i-j loop.
Флойд-Уоршелл находит, что 1→3 короче через 2 (2), чем напрямую (4) — важно для правильного подсчёта соседейFloyd-Warshall finds that 1→3 is shorter via 2 (2) than directly (4) — critical for correctly counting neighbors
После построения полной матрицы задача сводится к простому подсчёту: для каждого города i посчитать, сколько городов j (j≠i) имеют `dist[i][j] <= threshold`, и выбрать город с наименьшим таким числом. Здесь особенно важна деталь из диаграммы: расстояние от 1 до 3 напрямую равно 4, но через город 2 — всего 2 (1+1), и именно скорректированное Флойдом-Уоршеллом значение, а не сырые данные из `roads`, должно использоваться при подсчёте соседей в пределах порога.After building the full matrix, the problem reduces to simple counting: for each city i, count how many cities j (j≠i) have `dist[i][j] <= threshold`, and pick the city with the fewest. The diagram's detail matters here: the direct distance from 1 to 3 is 4, but via city 2 it's only 2 (1+1), and it's this Floyd-Warshall-corrected value, not the raw `roads` data, that must be used when counting neighbors within the threshold.
class Solution {
public:
int findCity(int n, std::vector<std::vector<int>>& roads, int threshold) {
const int INF = 1e9;
std::vector<std::vector<int>> dist(n, std::vector<int>(n, INF));
for (int i = 0; i < n; ++i) dist[i][i] = 0;
for (auto& r : roads) {
dist[r[0]][r[1]] = std::min(dist[r[0]][r[1]], r[2]);
dist[r[1]][r[0]] = std::min(dist[r[1]][r[0]], r[2]);
}
for (int k = 0; k < n; ++k) // Флойд-Уоршелл из 3.2.2// Floyd-Warshall from 3.2.2
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (dist[i][k] < INF && dist[k][j] < INF)
dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
int best = -1, bestCount = n + 1;
for (int i = 0; i < n; ++i) {
int count = 0;
for (int j = 0; j < n; ++j)
if (i != j && dist[i][j] <= threshold) count++;
if (count <= bestCount) { // "<=" — при равенстве побеждает больший номер города// "<=" — on a tie, the larger city number wins
bestCount = count;
best = i;
}
}
return best;
}
};Сложность O(n³) — та самая асимптотика Флойда-Уоршелла из 3.2.2, оправданная здесь именно потому, что n мало (город/регион из условия, не страна с миллионом перекрёстков) — ровно тот случай "матрица допустима", который 3.2.2 явно противопоставлял разреженным графам с большим n.Complexity is O(n³) — the exact Floyd-Warshall asymptotic from 3.2.2, justified here precisely because n is small (a city/region from the problem, not a country with a million intersections) — exactly the "matrix is acceptable" case 3.2.2 explicitly contrasted with sparse graphs at large n.
Как показано на диаграмме, расстояние 1→3 после Флойда-Уоршелла (2) меньше прямой дороги (4) — подсчёт "соседей в пределах threshold" по необработанному списку рёбер вместо посчитанной матрицы даст неверный (заниженный) результат, теряя более короткие пути через промежуточные города.As the diagram shows, the 1→3 distance after Floyd-Warshall (2) is shorter than the direct road (4) — counting "neighbors within threshold" from the raw edge list instead of the computed matrix gives a wrong (understated) result, missing shorter paths through intermediate cities.
Условие явно требует при равном числе достижимых городов выбирать БОЛЬШИЙ номер — использование строгого `count < bestCount` вместо `count <= bestCount` при переборе городов по возрастанию номера даст первый (меньший) город с минимальным count, а не последний (больший), что нарушает условие задачи в конкретном крайнем случае, который легко пропустить при беглом тестировании.The problem explicitly requires picking the LARGER number on a tie in reachable-city count — using strict `count < bestCount` instead of `count <= bestCount` while iterating cities in increasing order picks the first (smaller) city with the minimum count, not the last (larger) one, violating the problem statement in a specific edge case that's easy to miss with cursory testing.