fork download
copy 
  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. void dijkstra(int start, const vector<vector<pair<int,int>>>& graph, vector<int>& dist) {
  11.     int n = graph.size();
  12.     dist.assign(n, INF);
  13.     dist[start] = 0;
  14.  
  15.     // (odległość, wierzchołek)
  16.     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
  17.     pq.push({0, start});
  18.  
  19.     while (!pq.empty()) {
  20.         auto [d, u] = pq.top();
  21.         pq.pop();
  22.  
  23.         if (d > dist[u]) continue;
  24.  
  25.         for (auto [v, w] : graph[u]) {
  26.             if (dist[u] + w < dist[v]) {
  27.                 dist[v] = dist[u] + w;
  28.                 pq.push({dist[v], v});
  29.             }
  30.         }
  31.     }
  32. }
  33.  
  34. int main() {
  35.     // Przykładowy graf:
  36.     // 0 - A
  37.     // 1 - B
  38.     // 2 - C
  39.     // 3 - D
  40.     //
  41.     // Krawędzie:
  42.     // A-B (2), A-C (5), A-D (1)
  43.     // B-D (3)
  44.     // C-D (2)
  45.  
  46.     vector<vector<pair<int,int>>> graph(4);
  47.  
  48.     graph[0].push_back({1, 2}); // A -> B
  49.     graph[0].push_back({2, 5}); // A -> C
  50.     graph[0].push_back({3, 1}); // A -> D
  51.  
  52.     graph[1].push_back({0, 2}); // B -> A
  53.     graph[1].push_back({3, 3}); // B -> D
  54.  
  55.     graph[2].push_back({0, 5}); // C -> A
  56.     graph[2].push_back({3, 2}); // C -> D
  57.  
  58.     graph[3].push_back({0, 1}); // D -> A
  59.     graph[3].push_back({1, 3}); // D -> B
  60.     graph[3].push_back({2, 2}); // D -> C
  61.  
  62.     vector<int> dist;
  63.     dijkstra(0, graph, dist);
  64.  
  65.     cout << "Najkrotsze odleglosci od A:\n";
  66.     for (int i = 0; i < dist.size(); i++) {
  67.         cout << "A -> " << char('A' + i) << " = " << dist[i] << "\n";
  68.     }
  69.  
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Najkrotsze odleglosci od A:
A -> A = 0
A -> B = 2
A -> C = 3
A -> D = 1
https://ideone.com/AYQtvt
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!