DJ extra

void dijkstra(const map<int, vector<Edge>>& graph, int source, int target) {
    const int INF = numeric_limits<int>::max();
    map<int, int> dist;
    map<int, int> parent;

    for (const auto& [node, edges] : graph) {
        dist[node] = INF;
        parent[node] = -1;
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[source] = 0;
    pq.push({0, source});

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist[u]) continue;

        if (u == target) break;

        for (const auto& edge : graph.at(u)) {
            if (dist[u] + edge.cost < dist[edge.target]) {
                dist[edge.target] = dist[u] + edge.cost;
                parent[edge.target] = u;
                pq.push({dist[edge.target], edge.target});
            }
        }
    }

    if (dist[target] == INF) {
        cout << "Nie ma drogi z " << source << " do " << target << endl;
    } else {
        cout << "Najkrotszy koszt: " << dist[target] << endl;

        vector<int> path;
        for (int v = target; v != -1; v = parent[v]) {
            path.push_back(v);
        }
        reverse(path.begin(), path.end());

        cout << "Sciezka: ";
        for (int v : path) cout << v << " ";
        cout << endl;
    }
}