fork(1) download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <limits>
  5.  
  6. using namespace std;
  7.  
  8. const int INF = numeric_limits<int>::max();
  9.  
  10. vector<int> dijkstra(int start, const vector<vector<pair<int, int>>>& graph) {
  11.     int n = graph.size();
  12.     vector<int> dist(n, INF);
  13.     dist[start] = 0;
  14.  
  15.     // Kolejka priorytetowa (dystans, wierzchołek)
  16.     priority_queue<
  17.         pair<int, int>,
  18.         vector<pair<int, int>>,
  19.         greater<pair<int, int>>
  20.     > pq;
  21.  
  22.     pq.push({0, start});
  23.  
  24.     while (!pq.empty()) {
  25.         auto [currentDist, u] = pq.top();
  26.         pq.pop();
  27.  
  28.         // Jeśli istnieje lepsza droga – pomijamy
  29.         if (currentDist > dist[u]) continue;
  30.  
  31.         // Przegląd sąsiadów
  32.         for (auto [v, weight] : graph[u]) {
  33.             int newDist = currentDist + weight;
  34.  
  35.             if (newDist < dist[v]) {
  36.                 dist[v] = newDist;
  37.                 pq.push({newDist, v});
  38.             }
  39.         }
  40.     }
  41.  
  42.     return dist;
  43. }
  44.  
  45. int main() {
  46.     // Przykładowy graf (skierowany)
  47.     // Każdy element to: (sąsiad, waga)
  48.     vector<vector<pair<int, int>>> graph = {
  49.         {{1, 1}, {2, 4}},     // 0 -> 1 (1), 0 -> 2 (4)
  50.         {{2, 2}, {3, 5}},     // 1 -> 2 (2), 1 -> 3 (5)
  51.         {{3, 1}},             // 2 -> 3 (1)
  52.         {}                    // 3
  53.     };
  54.  
  55.     int start = 0;
  56.     vector<int> distances = dijkstra(start, graph);
  57.  
  58.     cout << "Najkrotsze odleglosci od wierzcholka " << start << ":\n";
  59.     for (int i = 0; i < distances.size(); i++) {
  60.         if (distances[i] == INF)
  61.             cout << i << ": INF\n";
  62.         else
  63.             cout << i << ": " << distances[i] << "\n";
  64.     }
  65.  
  66.     return 0;
  67. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin 
Standard input is empty
stdout 
Najkrotsze odleglosci od wierzcholka 0:
0: 0
1: 1
2: 3
3: 4
https://ideone.com/rY79Sc
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!