fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long INF = LLONG_MAX;
  5.  
  6. // Rekonstrukcja ścieżki z parent[]
  7. vector<int> get_path(int target, const vector<int> &parent) {
  8.     vector<int> path;
  9.     if (parent[target] == -1) return path;
  10.  
  11.     while (target != -1) {
  12.         path.push_back(target);
  13.         target = parent[target];
  14.     }
  15.     reverse(path.begin(), path.end());
  16.     return path;
  17. }
  18.  
  19. vector<long long> dijkstra(int n, vector<vector<pair<int,int>>> &adj, int s, vector<int> &parent) {
  20.     vector<long long> dist(n, INF);
  21.     dist[s] = 0;
  22.  
  23.     parent.assign(n, -1);
  24.  
  25.     priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
  26.     pq.push({0, s});
  27.  
  28.     while (!pq.empty()) {
  29.         auto [d, u] = pq.top();
  30.         pq.pop();
  31.  
  32.         if (d > dist[u]) continue;
  33.  
  34.         for (auto &[v, w] : adj[u]) {
  35.             if (dist[u] + w < dist[v]) {
  36.                 dist[v] = dist[u] + w;
  37.                 parent[v] = u;
  38.                 pq.push({dist[v], v});
  39.             }
  40.         }
  41.     }
  42.     return dist;
  43. }
  44.  
  45. int main() {
  46.     ios::sync_with_stdio(false);
  47.     cin.tie(nullptr);
  48.  
  49.     // ***** DEFINICJA GRAFU *****
  50.     int n = 6; // liczba wierzchołków (0..5)
  51.  
  52.     vector<vector<pair<int,int>>> adj(n);
  53.  
  54.     // Dodajemy krawędzie (u, v, w)
  55.     adj[0].push_back({1, 7});
  56.     adj[0].push_back({2, 9});
  57.     adj[1].push_back({3, 10});
  58.     adj[2].push_back({3, 5});
  59.     adj[3].push_back({4, 3});
  60.     adj[4].push_back({5, 1});
  61.  
  62.     // ***** ZDEFINIOWANA ŚCIEŻKA *****
  63.     int start = 0;
  64.     int target = 5;
  65.  
  66.     vector<int> parent;
  67.     vector<long long> dist = dijkstra(n, adj, start, parent);
  68.  
  69.     if (dist[target] == INF) {
  70.         cout << "Brak ścieżki.\n";
  71.         return 0;
  72.     }
  73.  
  74.     cout << "Najkrótsza odległość: " << dist[target] << "\n";
  75.  
  76.     vector<int> path = get_path(target, parent);
  77.  
  78.     cout << "Ścieżka: ";
  79.     for (int v : path) cout << v << " ";
  80.     cout << "\n";
  81.  
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Najkrótsza odległość: 18
Ścieżka: 0 2 3 4 5
https://ideone.com/pKgDSi
language:
C++ (gcc 8.3)
created:
6 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!