Autoputevi

U jednoj državi postoji mreža autoputeva koja povezuje njene gradove. Na deonici između svaka dva grada spojena autoputem postoje naplatne rampe, na kojima se naplaćuje putarina.

Porodica ide na odmor iz svog grada u drugi grad, poznat po svojim turističkim atrakcijama. Natočili su svoj rezervoar do vrha i ne moraju da brinu da li će imati goriva da stignu na svoje odredište, ali ipak žele da minimizuju pređeni put. Takođe, odredili su budžet koji su spremni da potroše na putarinu i ni jedna trasa koja ga prekoračuje nije prihvatljiva.

Pronaći optimalnu trasu za njihovo putovanje koristeći datu mrežu autoputeva.

Opis ulaza

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\) \(d\) \(c\), gde su \(u\) i \(v\) gradovi između kojih je deonica, \(d\) dužina deonice, a \(c\) cena putarine. Najzad, unose se početni i krajnji grad, kao i budžet za putarine.

Opis izlaza

Na standardni izlaz ispisati dužinu optimalne trase, a zatim i cenu putarine na njoj. U slučaju više trasa sa istom dužinom puta, ispisati onu sa manjom cenom putarine.

Primer

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

Zadatak se svodi na pronalaženje najkraćeg puta između dva čvora u neusmerenom grafu, pri čemu postoji uslov da se ne sme prekoračiti određena cena. Ovaj uslov nam ne dozvoljava da koristimo osnovnu verziju Dajkstrinog algoritma, već je potrebno izvršiti određene modifikacije.

Kako grane sada osim dužine sadrže i cenu, potrebno je čuvati red sa prioritetom trojki celih brojeva u koji ćemo ubacivati čvor do kog vodi tekuća grana, ukupnu dužinu, kao i cenu koja se dostiže koristeći datu granu. Red će sortirati elemente prvo po dužini, a zatim po ceni (u tekstu je naglašeno da ukoliko nađemo dva puta iste dužine, tada razmatramo cenu).

Pored reda sa prioritetom, čuvamo i vektore minimalnih dužina i cena za čvorove iz grafa u odnosu na početni čvor. Na početku su oni inicijalizovani tako da sadrže vrednost +za svaki od čvorova. U prvom koraku postavljamo minimalnu dužinu i cenu za početni čvor na 0 i dodajemo grane ka njegovim susedima u red.

U svakom sledećem koraku uzimamo jednu granu iz reda sa prioritetom i najpre proveravamo da li ona vodi ka ciljnom čvoru. Ukoliko vodi, znamo da je, zbog čuvanja u redu sa prioritetom, ona poslednja grana na optimalnom putu. Ukoliko ne vodi, treba da proverimo da li od čvora do kog ona vodi postoji bolji put do nekih od njegovih suseda, koji ne prekoračuje maksimalnu cenu. Ukoliko postoji, grane ka tim susedima treba da dodamo u red, a takođe i da ažuriramo minimalnu dužinu i/ili cenu do tih suseda.

Kako je algoritam modifikacija Dajkstrinog algoritma, njegova složenost je \(O((V + E) * log V)\).

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <tuple>

using namespace std;

class Graph {
private:
    int broj_cvorova;
    vector<vector<pair<int, pair<int, int>>>> lista_suseda; 
    
public:
    Graph(int broj_cvorova) {
        this->broj_cvorova = broj_cvorova;
        lista_suseda.resize(broj_cvorova);
    }

    void dodaj_granu(int u, int v, int dist, int cost) {
        lista_suseda[u].push_back({v, {dist, cost}});
        lista_suseda[v].push_back({u, {dist, cost}});
    }

    void dijkstra(int src, int dest, int budget) {
        // duzina, cena i cvor
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
        vector<int> dist(broj_cvorova, numeric_limits<int>::max()); 
        vector<int> min_cost(broj_cvorova, numeric_limits<int>::max()); 
 
        pq.push({0, 0, src});
        dist[src] = 0;
        min_cost[src] = 0;

        while (!pq.empty()) {
            auto [currDist, currCost, u] = pq.top();
            pq.pop();

            if (u == dest) {
                cout << currDist << " " << currCost << endl;
                return;
            }

            if (currDist > dist[u] || currCost > min_cost[u]) continue;

            for (auto& [v, weights] : lista_suseda[u]) {
                auto [d, c] = weights;
                int nextDist = currDist + d;
                int nextCost = currCost + c;

                if (nextCost <= budget && (nextDist < dist[v] || nextCost < min_cost[v])) {
                    dist[v] = nextDist;
                    min_cost[v] = nextCost;
                    pq.push({nextDist, nextCost, v});
                }
            }
        }

        cout << "-" << endl;
    }
};

int main() {

   int n, m;

   cin >> n >> m;

   Graph *G = new Graph(n);

   int u, v, d, c;
   for (int i = 0; i < m; i++) {
      cin >> u >> v >> d >> c;
      G->dodaj_granu(u, v, d, c);
   }

   int src, dest, budget;
   cin >> src >> dest >> budget;

   G->dijkstra(src, dest, budget);

   delete G;
   return 0;
}