fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // inf = 10^9
  5. const int inf = 1e9;
  6.  
  7. // Representasi graf dan setup-setup lainnya
  8. vector<pair<int, int>> adjList[100005];
  9. bool vis[100005];
  10. int dst[100005];
  11.  
  12. int main() {
  13.     // inputin graf
  14.     // n banyak node, m banyak jalan (edge), start : start dari node yg mana
  15.     int n, m, start;
  16.     cin >> n >> m >> start;
  17.     for(int i = 1; i <= m; i++) {
  18.         // u : start, v : end, w : weight (jarak)
  19.         int u, v, w;
  20.         cin >> u >> v >> w;
  21.         // undirected!! jadi butuh dua kali nyimpen (dari u ke v sama v ke u)
  22.         adjList[u].push_back(make_pair(v, w));
  23.         adjList[v].push_back(make_pair(u, w));
  24.     }
  25.     // set dst semua node (kecuali start) = inf, vis = false
  26.     for(int i = 0; i < n; i++) vis[i] = false, dst[i] = inf;
  27.     dst[start] = 0;
  28.     // algo dijalankan
  29.     // priority_queue dipake untuk menyimpan (dst[node], node) dari terkecil
  30.     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  31.     // masukin node start
  32.     pq.push(make_pair(dst[start], start));
  33.     while(!pq.empty()) {
  34.         // dapetin elemen teratas dari pq
  35.         int curnode = pq.top().second;
  36.         pq.pop();
  37.         if(vis[curnode] == true) continue;
  38.         // iterate semua neighbor dari curnode
  39.         for(auto i : adjList[curnode]) {
  40.             int nextnode = i.first, weight = i.second;
  41.             // kalo ternyata ada jarak yang minimum, kita update dan push ke pq
  42.             if(dst[nextnode] > dst[curnode] + weight) {
  43.                 dst[nextnode] = dst[curnode] + weight;
  44.                 pq.push(make_pair(dst[nextnode], nextnode));
  45.             }
  46.         }
  47.         // set visited = true
  48.         vis[curnode] = true;
  49.     }
  50.     for(int i = 0; i < n; i++) cout << dst[i] << ' ';
  51.     cout << '\n';
  52. }
Success #stdin #stdout 0.01s 5940KB
comments (?)
stdin
copy 
3 4
1 2 6
1 3 2
3 2 3
1 3 4
stdout
copy 
1000000000 0 1000000000
https://ideone.com/55zW0a
language:
C++ (gcc 8.3)
created:
12 hours 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!