Opis glavnog rešenja
Zadatak je moguće rešiti formiranjem odgovarajućeg grafa i pretragom tog grafa u širinu. Prirodno se nameće da čvorovi grafa budu stanice, a da između dve stanice postoji grana ako i samo ako postoji autobus na čijoj se ruti nalaze obe stanice. Međutim, ovakvo rešenje može biti neefikasno, jer je u slučaju dugačkih ruta potrebno u graf dodavati jako veliki broj grana, između svake dve stanice duž te rute (broj grana tada kvadratno zavisi od broja stanica na ruti). Zato je bolje izbeći direktno povezivanje stanica tako što se u graf pored čvorova koji predstavljaju stanice ubace i čvorovi koji predstavljaju autobuse.
Pretpostavimo da postoji 9 stanica i 3 autobusa. Prvi kruži rutom 1, 2, 5, 6, drugi rutom 2, 3, 7, 6, a treći rutom 3, 4, 9, 8, 7. Mapa ruta je prikazana na narednoj slici.
Na narednoj slici levo je prikazan graf koji opisuje povezanost između stanica, a desno graf koji opisuje povezanost između stanica (prikazanih kružnim čvorovima) i autobuskih linija (prikazanih kvadratnim čvorovima).
Algoritmom pretrage u širinu određujemo najkraće rastojanje između početne i krajnje stanice, vodeći posebno računa o tome da rastojanje povećavamo samo, na primer, prilikom prelaska sa čvora autobusa na čvor stanice (a ne sa čvora stanice na čvor autobusa).
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
enum Node_type { BUS, STATION };
class Graph {
private:
int number_of_buses;
// Za svaku stanicu pamtimo autobuse koji staju na njoj
unordered_map<int, vector<int>> buses_on_station;
// Za svaki autobus pamtimo stanice na kojima on staje. Indeks elementa u vektoru predstavlja redni broj autobusa
vector<vector<int>> stations_for_bus;
// Za svaku stanicu pamtimo broj voznji (presedanja/autobusa) koji je potreban da se dodje do te stanice
unordered_map<int, int> rides_to_station;
// Za svaki autobus pamtimo broj voznji (presedanja/autobusa) dok se ne ukrcamo na taj autobus
vector<int> rides_to_bus;
void add_station_for_bus(int bus, int station) {
stations_for_bus[bus].push_back(station);
}
void add_bus_for_station(int bus, int station) {
buses_on_station[station].push_back(bus);
}
public:
Graph(int number_of_buses) {
this->number_of_buses = number_of_buses;
rides_to_bus.resize(number_of_buses, -1);
}
void pair_bus_and_station(int bus, int station) {
add_bus_for_station(bus, station);
add_station_for_bus(bus, station);
}
int find_min_number_of_rides(int start_station, int end_station) {
int min_number_of_rides = -1;
Node_type STATION_NODE = STATION;
Node_type BUS_NODE = BUS;
// U redu cemo cuvati podatak o tome da li smo trenutno u nekom autobusu ili na stanici
// (kao i redni broj autobusa/stanice)
queue<pair<Node_type, int>> q;
q.emplace(STATION_NODE, start_station);
rides_to_station[start_station] = 0;
while (!q.empty()) {
[node_type, number_of_bus_or_station] = q.front();
q.pop();
if (node_type == STATION && number_of_bus_or_station == end_station) {
min_number_of_rides = rides_to_station[number_of_bus_or_station];
break;
}
// Ako smo trenutno na nekoj stanici
if (node_type == STATION) {
int station = number_of_bus_or_station;
// Gledamo koji sve autobusi staju na toj stanici
for (int bus : buses_on_station[station]) {
// Ako nismo vec ulazili u neki autobus, zelimo da udjemo u taj autobus i vozimo se njim
if (rides_to_bus[bus] == -1) {
// Broj menjanja autobusa da bi se doslo do trenutnog autobusa je jednak broju promena autobusa koji je
// potreban da se dodje do trenutne stanice. Svi autobusi kruze po nekim stanicama, tako da je broj promena
// autobusa da bi se doslo do svih stanica kojima prolazi jedan autobus jednak
rides_to_bus[bus] = rides_to_station[station];
q.emplace(BUS, bus);
}
}
}
// Inace, ako smo trenutno u nekom autobusu
else if (node_type == BUS) {
int bus = number_of_bus_or_station;
// Gledamo na kojim stanicama staje taj autobus
for (int station : stations_for_bus[bus]) {
// Za svaku stanicu na kojoj nismo vec bili, izlazimo na njoj. Broj voznji (menjanja autobusa do date stanice)
// se povecava samo za 1, jer smo trenutnim autobusom dosli do nje sto je jos jedan autobus u odnosu na
// prethodno stanje. Kada smo vec na nekoj stanici koja je na putu istog autobusa, nema presedanja, pa se tu
// brojac ne uvecava
if (rides_to_station.find(station) == rides_to_station.end()) {
rides_to_station[station] = rides_to_bus[bus] + 1;
q.emplace(STATION, station);
}
}
}
}
return min_number_of_rides;
}
};
int main() {
ios_base::sync_with_stdio(false);
int number_of_buses;
cin >> number_of_buses;
Graph *G = new Graph(number_of_buses);
int number_of_stations, station;
for (int bus = 0; bus < number_of_buses; bus++) {
cin >> number_of_stations;
for (int i = 0; i < number_of_stations; i++) {
cin >> station;
G->pair_bus_and_station(bus, station);
}
}
int start_station, end_station;
cin >> start_station >> end_station;
cout << G->find_min_number_of_rides(start_station, end_station) << endl;
delete G;
return 0;
}