fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long INF = LLONG_MAX;
  5.  
  6. // Dijkstra: znajdź najkrótsze odległości od wierzchołka startowego 's'
  7. vector<long long> dijkstra(int n, vector<vector<pair<int,int>>> &adj, int s) {
  8.     vector<long long> dist(n, INF);
  9.     dist[s] = 0;
  10.  
  11.     // priority_queue: (odległość, wierzchołek)
  12.     priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
  13.     pq.push({0, s});
  14.  
  15.     while (!pq.empty()) {
  16.         auto [d, u] = pq.top();
  17.         pq.pop();
  18.  
  19.         // Jeśli znaleźliśmy lepszą ścieżkę wcześniej, pomijamy
  20.         if (d > dist[u]) continue;
  21.  
  22.         for (auto &[v, w] : adj[u]) {
  23.             if (dist[u] + w < dist[v]) {
  24.                 dist[v] = dist[u] + w;
  25.                 pq.push({dist[v], v});
  26.             }
  27.         }
  28.     }
  29.  
  30.     return dist;
  31. }
  32.  
  33. int main() {
  34.     ios::sync_with_stdio(false);
  35.     cin.tie(nullptr);
  36.  
  37.     int n, m;
  38.     cin >> n >> m;
  39.  
  40.     vector<vector<pair<int,int>>> adj(n);
  41.  
  42.     // Wczytywanie grafu (u, v, w) – krawędź skierowana lub nieskierowana
  43.     for (int i = 0; i < m; i++) {
  44.         int u, v, w;
  45.         cin >> u >> v >> w;
  46.         adj[u].push_back({v, w});
  47.         // Jeśli graf nieskierowany, dodaj też:
  48.         // adj[v].push_back({u, w});
  49.     }
  50.  
  51.     int start;
  52.     cin >> start;
  53.  
  54.     vector<long long> dist = dijkstra(n, adj, start);
  55.  
  56.     // Wypisanie wyników
  57.     for (int i = 0; i < n; i++) {
  58.         if (dist[i] == INF) cout << "INF\n";
  59.         else cout << dist[i] << "\n";
  60.     }
  61.  
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
3 5 76 8 2 0
stdout 
INF
INF
0
https://ideone.com/TzB4aE
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!