fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 1e9;
  5.  
  6. int main() {
  7.     // Liczba wierzchołków
  8.     int n = 6;
  9.  
  10.     // Lista krawędzi: (from, to, weight)
  11.     vector<tuple<int,int,int>> edges = {
  12.         {0, 1, 4},
  13.         {0, 2, 2},
  14.         {1, 2, 5},
  15.         {1, 3, 10},
  16.         {2, 4, 3},
  17.         {4, 3, 4},
  18.         {3, 5, 11}
  19.     };
  20.  
  21.     // Budowa grafu
  22.     vector<vector<pair<int,int>>> graph(n);
  23.     for (auto [a, b, w] : edges) {
  24.         graph[a].push_back({b, w});
  25.         graph[b].push_back({a, w}); // usuń, jeśli graf skierowany
  26.     }
  27.  
  28.     // Dijkstra od wierzchołka 0
  29.     vector<int> dist(n, INF);
  30.     dist[0] = 0;
  31.  
  32.     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
  33.     pq.push({0, 0});
  34.  
  35.     while (!pq.empty()) {
  36.         auto [d, v] = pq.top();
  37.         pq.pop();
  38.  
  39.         if (d > dist[v]) continue;
  40.  
  41.         for (auto [to, w] : graph[v]) {
  42.             if (dist[to] > dist[v] + w) {
  43.                 dist[to] = dist[v] + w;
  44.                 pq.push({dist[to], to});
  45.             }
  46.         }
  47.     }
  48.  
  49.     // Wyniki
  50.     cout << "Najkrotsze sciezki od wierzcholka 0:\n";
  51.     for (int i = 0; i < n; i++) {
  52.         if (dist[i] == INF)
  53.             cout << "Do " << i << ": brak drogi\n";
  54.         else
  55.             cout << "Do " << i << ": " << dist[i] << endl;
  56.     }
  57.  
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
Standard input is empty
stdout 
Najkrotsze sciezki od wierzcholka 0:
Do 0: 0
Do 1: 4
Do 2: 2
Do 3: 9
Do 4: 5
Do 5: 20
https://ideone.com/zoRJLm
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!