javni_prevoz

Milivoje se preselio u novi grad. On želi da koristi javni prevoz u ovom gradu. Pravila prevoza su sledeća:

  1. Svaki par povezanih stanica je povezan linijom javnog prevoza koja može da ide u oba smera.
  2. Ako Milivoje ide od stanice A do stanice B, potrebno je samo da plati razliku između cene puta od A do B, i ukupne cene koja je bila potrebna da se dođe do stanice A. Na primer, ako je do stanice A došao po ceni 1000 a od stanice A do stanice B je cena 1200 on treba da plati samo 200. Ukoliko je razlika negativna, cena puta je 0, odnosno besplatno može da se preveze od A do B.

Milivoje nema dovoljno novca, i potrebna mu je pomoc da dođe od prve do poslednje stanice a da potroši najmanje novca. Pomozite Milivoju!

Opis ulaza

Sa standardnog ulaza se unosi broj \(n\) koji predstavlja broj stanica (stanice su numerisane od 1 do n), zatim i broj \(m\) koji predstavlja broj linija javnog prevoza. Zatim se unosi \(m\) trojki brojeva (\(a\), \(b\), i \(c\)) koji predstavljaju stanice koje su povezane, kao i cenu puta od jedne stanice do druge.

Opis izlaza

Na standardni izlaz ispisati jedan broj koji predstavlja najjeftiniji put od stanice 1 do stanice \(n\) ukoliko Milivoje koristi javni prevoz.

Primer

Ulaz

5 5
1 2 60
3 5 70
1 4 120
4 5 150
2 3 80

Izlaz

80

Rešenje

Opis glavnog rešenja

U ovom bloku se opisuje glavno rešenje zadatka.

#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) {
      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});
   }

   int dijkstra(int u, int v) {
      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 (nadjeni_putevi[sused.first]) {
               continue;
            }

            int cena = sused.second < udaljenosti[tmp.second] ? 0 : (sused.second - udaljenosti[tmp.second]);
            if (udaljenosti[sused.first] > udaljenosti[tmp.second] + cena) {
               udaljenosti[sused.first] = udaljenosti[tmp.second] + cena;
               hip.push(std::make_pair(udaljenosti[sused.first], sused.first));
            }
         }
      }

      return udaljenosti[v];
   }
};

int main() {
   int n, m, x, y, w;

   std::cin >> n >> m;

   Graph g(n);

   for (int i = 0; i < m; i++) {
      std::cin >> x >> y >> w;
      g.dodaj_granu(x, y, w);
   }

   std::cout << g.dijkstra(1, n) << "\n";
}