fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. typedef pair<int, int> pii;  // Para (waga, wierzchołek)
  9.  
  10. void dijkstra(int start, int n, const vector<vector<pii>>& graph) {
  11.     vector<int> dist(n, INT_MAX);  // Tablica odległości
  12.     dist[start] = 0;
  13.  
  14.     priority_queue<pii, vector<pii>, greater<pii>> pq;  // Kolejka priorytetowa
  15.     pq.push({0, start});
  16.  
  17.     while (!pq.empty()) {
  18.         int u = pq.top().second;
  19.         int d = pq.top().first;
  20.         pq.pop();
  21.  
  22.         // Jeśli już znaleźliśmy mniejszą odległość, pomijamy ten wierzchołek
  23.         if (d > dist[u]) {
  24.             continue;
  25.         }
  26.  
  27.         // Przechodzimy po sąsiednich wierzchołkach
  28.         for (const auto& neighbor : graph[u]) {
  29.             int v = neighbor.second;  // Wierzchołek sąsiedni
  30.             int weight = neighbor.first;  // Waga krawędzi
  31.  
  32.             // Relaksacja krawędzi
  33.             if (dist[u] + weight < dist[v]) {
  34.                 dist[v] = dist[u] + weight;
  35.                 pq.push({dist[v], v});
  36.             }
  37.         }
  38.     }
  39.  
  40.     // Wypisujemy najkrótsze odległości
  41.     for (int i = 0; i < n; ++i) {
  42.         if (dist[i] == INT_MAX) {
  43.             cout << "Brak drogi do wierzchołka " << i << endl;
  44.         } else {
  45.             cout << "Odległość od wierzchołka " << start << " do " << i << " wynosi: " << dist[i] << endl;
  46.         }
  47.     }
  48. }
  49.  
  50. int main() {
  51.     int n, m;  // n - liczba wierzchołków, m - liczba krawędzi
  52.     cout << "Podaj liczbę wierzchołków i krawędzi: ";
  53.     cin >> n >> m;
  54.  
  55.     vector<vector<pii>> graph(n);
  56.  
  57.     cout << "Podaj krawędzie (wierzchołek1, wierzchołek2, waga):" << endl;
  58.     for (int i = 0; i < m; ++i) {
  59.         int u, v, weight;
  60.         cin >> u >> v >> weight;
  61.         graph[u].push_back({weight, v});
  62.         graph[v].push_back({weight, u});  // Ponieważ graf jest nieskierowany
  63.     }
  64.  
  65.     int start;
  66.     cout << "Podaj wierzchołek początkowy: ";
  67.     cin >> start;
  68.  
  69.     dijkstra(start, n, graph);
  70.  
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
4 2
0 1 7
2 3 5
0
stdout
copy 
Podaj liczbę wierzchołków i krawędzi: Podaj krawędzie (wierzchołek1, wierzchołek2, waga):
Podaj wierzchołek początkowy: Odległość od wierzchołka 0 do 0 wynosi: 0
Odległość od wierzchołka 0 do 1 wynosi: 7
Brak drogi do wierzchołka 2
Brak drogi do wierzchołka 3
https://ideone.com/etnXZL
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!