Vozovi

U jednoj državi postoji \(n\) gradova, numerisanih od \(1\) do \(n\). Grad \(1\) je glavni grad.

Postoji \(m\) puteva između gradova. Svaki put povezuje gradove \(u\) i \(v\), i njegova dužina je \(x\).

Pored puteva, postoji i \(k\) železničkih linija (vozova). Svaka linija direktno povezuje glavni grad (grad \(1\)) sa nekim gradom \(s\), a njena dužina je \(y\).

Država želi da smanji troškove održavanja i planira da ukine neke železničke linije. Međutim, želi da važi sledeći uslov:

Opis ulaza

U prvom redu nalaze se tri cela broja \(n\), \(m\) i \(k\) — broj gradova, broj puteva i broj železničkih linija.

U narednih \(m\) redova nalaze se po tri cela broja \(u\), \(v\) i \(x\) — koji označavaju da postoji put između gradova \(u\) i \(v\) dužine \(x\).

U narednih \(k\) redova nalaze se po dva cela broja \(s\) i \(y\) — grad do kog ide voz iz glavnog grada i dužina te linije.

Opis izlaza

Na standardni izlaz ispisati maksimalan broj železničkih linija koje je moguće ukinuti.

Primer

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

Kako bismo rešili zadatak, dovoljno je da pronađemo dužine najkraćih puteva od glavnog grada do svih ostalih gradova. Železničku liniju smemo da obrišemo samo ukoliko je njena dužina veća ili jednaka od dužine najkraćeg puta za dati grad.

Za nalaženje najkraćih puteva od glavnog grada do svih drugih gradova koristimo Dajkstrin algoritam složenosti O(\((|V|+|E|) \log |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 dijkstra(int start) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, poredjenje> hip;
        udaljenosti[start] = 0;
        hip.push({udaljenosti[start], start});

        while (!hip.empty()) {
            auto tmp = hip.top();
            hip.pop();
            int u = tmp.second;

            if (nadjeni_putevi[u]) {
                continue;
            }

            nadjeni_putevi[u] = true;

            for (pair<int, int> &sused : lista_suseda[u]) {
                int v = sused.first, weight = sused.second;
                if (udaljenosti[v] > udaljenosti[u] + weight) {
                    udaljenosti[v] = udaljenosti[u] + weight;
                    hip.push(make_pair(udaljenosti[v], v));
                }
            }
        }
    }

    int broj_ukinutih_vozova(int k, vector<pair<int, int>> pruge) {
        
        dijkstra(0);
        
        int uklanjanje = 0;
        for (auto [grad, duzina] : pruge){
            if(udaljenosti[grad] <= duzina)
               uklanjanje++;
         }   

        return uklanjanje;
    }
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    Graph *G = new Graph(n);

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

    vector<pair<int, int>> pruge;
    for (int i = 0; i < k; i++) {
        int s, y;
        cin >> s >> y; 
        pruge.push_back({s-1, y}); 
    }

    cout << G->broj_ukinutih_vozova(k, pruge) << "\n";

    delete G;
    return 0;
}