Putnik želi da putuje avionom od grada \(A\) do grada \(B\). Postoje različite avio kompanije koje nude letove između ovih gradova, a svaki let ima svoju cenu. Putnik ima mogućnost da bira između različitih ruta i avio-kompanija u skladu sa svojim preferencijama i budžetom. Između nekih gradova postoje direktni letovi, dok je, da bi se došlo do nekih gradova, potrebno vrsiti presedanja. Putnik želi da potroši što je moguće manje novca. Takođe, on može da izabere grad koji obavezno želi da poseti na putu od \(A\) do \(B\), a i da zada grad u kome ne želi nikako da boravi na tom putu.
Sa standardnog ulaza se unose vrednosti \(n\) i \(m\) koje predstavljaju broj gradova i broj letova među njima. Nakon toga se unose po tri vrednosti koje predstavljaju početni, krajnji grad leta, kao i njegovu cenu. Nakon toga se unosi vrednost \(q\) koja predstavlja broj pojedinačnih putovanja. Zatim se za svako od q pojedinačnih putovanja unose po četiri vrednosti koje predstavljaju početni i krajnji grad putovanja, kao i grad preko koga putnik želi da putuje, i grad preko koga nikako ne želi da prođe.
Na standardni izlaz za svaki od upita ispisati minimalnu cenu leta od početnog do krajnjeg grada koji zadovoljava date uslove.
9 14 0 1 4 0 7 8 1 2 8 1 7 11 2 3 7 2 5 4 2 8 2 3 4 9 3 5 14 4 5 10 5 6 2 6 7 1 6 8 6 7 8 7 3 0 4 6 3 0 4 2 6 0 4 6 5
21 26 33
Problem možemo podeliti na dva potproblema. Jedan je kako naći najkraći put od čvora \(u\) do čvora \(v\) preko čvora \(w\) i drugi kako da nađemo najkraći put od \(u\) do \(v\) a da nikako ne prolazimo kroz \(w\). Algoritam koji nam može pomoći kako da nađemo najkraći put od čvora do nekog drugog čvora (ili svih drugih čvorova) je Dajkstrin algoritam. Ovde je potrebno napraviti malu modifikaciju osnovne varijante algoritma.
Najlakši način da nađemo put od \(u\) do \(v\) preko \(w\) je da 2 puta pokrenemo algoritam pri čemu prvi put tražimo najkraći put od \(u\) do \(w\), dok drugi put tražimo najkraći put od \(w\) do \(v\). Na ovaj način najkraći put od \(u\) do \(v\) sigurno prolazi kroz \(w\). Kako je za korektnost Dajkstrinog algoritma potrebna početna konfiguracija u kojoj ni do jednog čvora nemamo najkraći put i svi čvorovi su na početku nedostižni (odnosno najkraći put do njih je 0), potrebno je između 2 pokretanja algoritma resetovati graf, odnosno dovesti ga u početnu konfiguraciju.
Slučaj u kome je potrebno da preko nekog čvora \(w\) nikako ne idemo na najkraćem putu od \(u\) do \(v\) možemo jednostavno implementirati tako što nikada nećemo ažurirati pud od \(w\). Kada iz reda sa prioritetom uzmemo čvor \(a\) koji ima suseda \(w\), prosto ne ažuriramo put do \(w\). Na ovaj način, središnji čvor (koji izbegavamo) uvek ima dužinu najkraćeg puta beskonačno, što znači da je on nedostižan, pa samim tim nikada najkraći put od \(u\) do \(v\) ne može uključivati čvor \(w\).
Dodatno treba obratiti pažnju na jednu sitnicu. Postoji veći broj upita u kojima pokrećemo algoritam. Kako graf mora da bude u početnoj konfiguraciji za svako pokretanje, potrebno je i nakon svakog upita resetovati grafi i dovesti ga u početno stanje.
Dajkstrin algoritam u čijoj implementacijij koristimo red sa prioritetom (min hip) je složenosti \(O((V + E) * V)\). Ukupan broj pokretanja algoritma je dva za svaki od \(q\) upita pa je složenost celog rešenja \(O(q * (V + E) * V)\).
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
#define INFINITY numeric_limits<int>::max()
using namespace std;
struct poredjenje
{
bool operator()(const pair<int, int> &p1, const pair<int, int> &p2)
{
return p1.first > p2.first;
}
};
class Graph {
private:
int broj_cvorova;
vector<vector<pair<int, int>>> lista_suseda;
vector<int> udaljenosti;
vector<bool> nadjeni_putevi;
public:
Graph(int broj_cvorova) {
this->broj_cvorova = broj_cvorova;
lista_suseda.resize(broj_cvorova);
udaljenosti.resize(broj_cvorova, INFINITY);
nadjeni_putevi.resize(broj_cvorova, false);
}
void dodaj_granu(int u, int v, int w) {
lista_suseda[u].push_back({v, w});
lista_suseda[v].push_back({u, w});
}
void resetuj_graf() {
fill(udaljenosti.begin(), udaljenosti.end(), INFINITY);
fill(nadjeni_putevi.begin(), nadjeni_putevi.end(), false);
}
int dijkstra(int u, int v, int izbegni) {
priority_queue<pair<int, int>, vector<pair<int, int>>, poredjenje> hip;
udaljenosti[u] = 0;
hip.push(make_pair(udaljenosti[u], u));
pair<int, int> tmp;
while (!hip.empty()) {
tmp = hip.top();
hip.pop();
if (nadjeni_putevi[tmp.second]) {
continue;
}
nadjeni_putevi[tmp.second] = true;
for (pair<int, int> &sused : lista_suseda[tmp.second]) {
if (sused.first == izbegni) {
continue;
}
if (udaljenosti[sused.first] > udaljenosti[tmp.second] + sused.second) {
udaljenosti[sused.first] = udaljenosti[tmp.second] + sused.second;
hip.push(make_pair(udaljenosti[sused.first], sused.first));
}
}
}
return udaljenosti[v];
}
int najjeftiniji_let(int u, int v, int idi_do, int izbegni) {
resetuj_graf();
int rezultat = dijkstra(u, idi_do, izbegni);
resetuj_graf();
return rezultat + dijkstra(idi_do, v, izbegni);
}
};
int main ()
{
int n, m;
cin >> n >> m;
Graph *G = new Graph(n);
int u, v, w;
for (int i = 0; i < m; i++) {
cin >> u >> v >> w;
G->dodaj_granu(u, v, w);
}
int q;
cin >> q;
int a, b, idi_do, izbegni;
while (q--) {
cin >> a >> b >> idi_do >> izbegni;
cout << G->najjeftiniji_let(a, b, idi_do, izbegni) << "\n";
}
delete G;
return 0;
}