Zadatak turističkog vodiča je da vodi turiste iz jednog grada u drugi. On ima mapu svih gradova u ponudi koji su povezani dvosmernim putevima. Između svaka dva grada postoji autobuska linija koja ima određeni kapacitet putnika. Potrebno je za proizvoljnu grupu turista i početni i krajnji grad odrediti broj putovanja potrebnih da sve turiste vodič dovede do ciljnog grada.
Sa standradnog ulaza unose se redom brojevi \(n\) i \(m\) (\(1 \leq n, m \leq 10^5\)), koji predstavljaju broj gradova i broj deonica između njih. Nakon toga se unosi \(m\) deonica, svaka u svojoj liniji, u formatu \(u\) \(v\) \(c\), gde su \(u\) i \(v\) gradovi između kojih je deonica, a \(c\) kapacitet prevoza. Nakon toga, unosi se pozitivn ceo broj \(q\), a zatim i \(q\) upita oblika \(p\) \(k\) \(t\), gde je \(p\) početni, \(k\) krajnji grad, a \(k\) broj turista, svaki u svom redu.
Ispisati za svaki upit u svom redu koliko je putovanja potrebno da se sprovedu svi turisti od početnog do krajnjeg grada.
7 10 1 2 30 1 3 15 1 4 10 2 4 25 2 5 60 3 4 40 3 6 20 4 7 35 5 7 20 6 7 30 2 1 7 99 2 6 50
4 2
Zadatak se može rešiti korišćenjem modifikovanog Flojd-Varšalovog algoritma. Ideja je da čuvamo za svaki par čvorova maksimalan broj putnika koji se mogu sprovesti od jednog do drugog čvora iz jednog puta. Kada primenimo algoritam, ostaje da za svaki upit ukupan broj turista podelimo maksimalnim brojem turista koji možemo da sprovedemo od prvog do poslednjeg grada.
Složenost ovog pristupa je \(O(|V|^3)\), jer pokrećemo samo jednu instancu Flojd-Varšalovog algoritma.
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <math.h>
using namespace std;
class Graph {
private:
int broj_cvorova;
vector<vector<int>> matrica_suseda;
public:
Graph(int broj_cvorova) {
this->broj_cvorova = broj_cvorova;
matrica_suseda.resize(broj_cvorova);
for(int i = 0; i < broj_cvorova; i++)
matrica_suseda[i].resize(broj_cvorova, 0);
}
void dodaj_granu(int u, int v, int weight) {
matrica_suseda[u][v] = weight;
matrica_suseda[v][u] = weight;
}
void floyd_warshall() {
for(int k = 0; k < broj_cvorova; k++){
for(int i = 0; i < broj_cvorova; i++){
for(int j = 0; j < broj_cvorova; j++){
matrica_suseda[i][j] = max(matrica_suseda[i][j],
min(matrica_suseda[i][k], matrica_suseda[k][j]));
}
}
}
}
int broj_putovanja(int p, int k, int t){
return ceil((float)t/matrica_suseda[p][k]);
}
};
int main() {
int n, m;
cin >> n >> m;
Graph *G = new Graph(n);
int u, v, t;
for(int i=0;i<m;i++){
cin >> u >> v >> t;
G->dodaj_granu(u-1, v-1, t);
}
G->floyd_warshall();
int q;
cin >> q;
while(q--){
int p, k, t;
cin >> p >> k >> t;
cout << G->broj_putovanja(p-1, k-1, t) << endl;
}
delete G;
return 0;
}