Например Apache Xerces / Xalan.
Он вроде и для C++ существует (я для Java использовал).

http://xerces.apache.org/#xerces-c

Dimitry SibiryakovmaytonВобщем если ты доберешся до этой части то там будет самый настоящий треш.

Для сугубо учебной задачи особого трэша там не будет, поскольку вряд ли в задании будет
идти минимизация времени поездки (для неё нужно гораздо больше информации, чем есть). Судя
по упоминанию цены, это определение самого выгодного маршрута в плане денег. Значит можно
сделать граф со станциями в качестве вершин и маршрутами в качестве рёбер. Остальное дело
техники.

Не понятно )))

"...время отправления /прибытия..." ( C ) автор

говорит как бы о том, что есть желания "согласовывать" пересадки. Т.е. время поездки (и пересадок) возможно значимо.

Лично я похожую задачу решал в две стадии. Сначала находил все маршруты (было ограничение на кол-во пересадок), потом по маршрутам пытался согласовать время пересадки.

Строить граф с учетом времени, это уж сильно большой граф получается ((( IMHO Проще время вторым шагом обрабатывать. Тут правда еще есть проблема перехода через границу суток.

p.s. но у меня проект завершился на примерно 700 Kb работающих исходных кодов (+служебный код, эксперементы - еще 400-500 Kb) ))))

Dimitry SibiryakovОн, конечно, получается больше....но всё равно это не так уж и сложно. В 700к исходников должно уложиться вместе со всей сервисной
обвязкой.

Проблема не в сложности програмного кода, а в сложности вычислений.

Одно дело поиск маршрута по графу с 50 000 - 110 000 ребрами, а другое дело, по графу в несколько раз больше

Из Сиднея в Мельбурн некоторые авиа рейсы происходят раз в 15-20 минут. Скоростные поезда ходят примерно аналогично. Т.е. вместо одного ребра, получится черти что.

Кроме того, с одного рейса можно успеть на 100500 рейсов которые происходят после него. Т.ч. еще и теоретически не очень понятно, как же результирующий граф должен выглядить. Вариант "ближайший рейс на отправку" - не вариант. Т.к. если мы прибываем на станцию в 13:59, а рейс на который нужно пересесть, отправляется в 14:00 - то это не айс, мы телепортироваться между перронами не успеем ))))

По факту, после "коннекта по времени" у меня получилась до десятков миллионов вариантов пересадок (если посередине попадал перелет Сидней - Мелбурн ))) ). Представлять все эти десятки миллионов вариантов как ребра графа - безумее.

AFAIK

Dimitry SibiryakovОн, конечно, получается больше, поскольку в качестве вершин придётся принимать моменты
прибытия-отправления.....

AFAIK больше на 2-3 порядка. Соответственно и вычислительные затраты и потребление памяти - скорее всего будут так же резко больше. IMHO.