294 [ Главку

bool skip; используется при возврате

FlightlnfoО { from = ; to = ; distance = 0; skip = false;

Flightlnfo(string f, string t, int d) { from = f; to = t; distance = d; skip = false;

const int MAXDIST = 100000;

Находит рейсы с помощью метода наименьшей стоимости, class Optimal {

Этот вектор содержит информацию о рейсах.

vector<FlightInfо> flights;

Этот стек используется для возврата. stack<FlightInfo> btStack;

Этот стек содержит оптимальное решение. stack<FlightInfо> optimal;

int minDist;

Если есть рейс между from и to,

запоминает расстояние в dist.

Возвращает true, если рейс существует,

и false - в противном случае.

bool match(string from, string to, int &dist);

Версия для поиска с помощью метода наименьшей стоимости.

II При заданном from находит самый короткий рейс.

Возвращает true, если рейс найден,

и false - в противном случае.

bool find(string from, Flightlnfo &f);

public:

Конструктор Optimal 0 {

minDist = MAXDIST;

Помещает полеты в базу данных.

void addflight(string from, string to, int dist) { flights.pushback(FlightInfo(from, to, dist));

Показывает маршрут и общую длину, void route();

Отображает оптимальный маршрут, void Optimal::showQpt();

Определяет, есть ли маршрут между from и to. void findroute(string from, string to);

Возвращает true, если маршрут бьш найден, bool routefoundo

return btstack.size О != 0;

Показывает маршрут и его длину.

void Optimal::route О

stack<FlightInfo> optTenp; int dist = 0; Flightlnfo f;

296 лава>

Меняет порядок стека на противоположный для отображения маршрута, while(!btStack.enpty()) {

f = btStack.top();

optTenp.push(f);

btStack.popO ;

dist += f.distance;

Если короче, то запоминает этот маршрут, if(minDist > dist) {

optimal = optTenp;

minDist = dist;

Отображает оптимальный маршрут.

void Optimal::showCpt()

Flightlnfo f; int dist =0;

cout Optimal solution is:\n ;

Отображает оптимальный маршрут, while(!optimal.enpty()) {

f = optimal.top О;

optimal.popO ;

cout f.from to ;

dist += f.distance;

cout f.to endl;

cout Distance is dist endl;

Если есть рейс между from и to,

запоминает расстояние в dist.

Возврашает true, если рейс существует,

и false - в противном случае.