fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 1e9;
  5.  
  6. int main() {
  7.     int n, m; // n - liczba wierzchołków, m - liczba krawędzi
  8.     cin >> n >> m;
  9.  
  10.     vector<vector<pair<int,int>>> graf(n + 1);
  11.     // pair = (sąsiad, waga)
  12.  
  13.     for(int i = 0; i < m; i++) {
  14.         int a, b, w;
  15.         cin >> a >> b >> w;
  16.         graf[a].push_back({b, w});
  17.         graf[b].push_back({a, w}); // usuń, jeśli graf skierowany
  18.     }
  19.  
  20.     int start;
  21.     cin >> start;
  22.  
  23.     vector<int> dist(n + 1, INF);
  24.     dist[start] = 0;
  25.  
  26.     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
  27.     // (odległość, wierzchołek)
  28.     pq.push({0, start});
  29.  
  30.     while(!pq.empty()) {
  31.         auto [d, v] = pq.top();
  32.         pq.pop();
  33.  
  34.         if(d > dist[v]) continue;
  35.  
  36.         for(auto [to, w] : graf[v]) {
  37.             if(dist[to] > dist[v] + w) {
  38.                 dist[to] = dist[v] + w;
  39.                 pq.push({dist[to], to});
  40.             }
  41.         }
  42.     }
  43.  
  44.     // Wyniki
  45.     for(int i = 1; i <= n; i++) {
  46.         if(dist[i] == INF) 
  47.             cout << "Brak drogi do " << i << endl;
  48.         else
  49.             cout << "Najkrotsza droga do " << i << " = " << dist[i] << endl;
  50.     }
  51.  
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
5 6
1 2 4
1 3 2
2 3 5
2 4 10
3 5 3
4 5 4
1
stdout
copy 
Najkrotsza droga do 1 = 0
Najkrotsza droga do 2 = 4
Najkrotsza droga do 3 = 2
Najkrotsza droga do 4 = 9
Najkrotsza droga do 5 = 5
https://ideone.com/ppWDa8
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!