retracing path in dijstra 
Разница между en1 и en2, 1 символ(ов) изменены
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll  long long↵
#define ar array↵
 ↵
const int mxa = 1e5 + 1;↵
ll a, b, c, n, m;↵
vector <ar<ll, 2>> adj[mxa];↵
ll dist[mxa];↵
 ↵
 ↵
 ↵
int main() {↵
 ↵
  cin >> n >> m;↵
  for (int i = 0; i < m; i++) {↵
    cin >> a >> b >> c; --a, --b;↵
    adj[a].push_back({c, b});↵
 ↵
  }↵
 ↵
  memset(dist, 0x3f, sizeof(dist));↵
 ↵
  priority_queue< ar<ll, 2>  , vector<ar<ll, 2>>, greater<ar<ll, 2>> > pq;↵
  dist[0] = 0;↵
  pq.push({0, 0});↵
  while (pq.size()) {↵
 ↵
    ar<ll, 2> node = pq.top();↵
    pq.pop();↵
 ↵
    if (node[0] > dist[node[1]])continue;↵
 ↵
    for ( ar<ll, 2> child : adj[node[1]]) {↵
 ↵
      if (dist[child[1]] > node[0] + child[0]) {↵
        dist[child[1]] = node[0] + child[0];↵
        pq.push({dist[child[1]], child[1]});↵
      }↵
    }↵
 ↵
  }↵
 ↵
  for (int i = 0; i < n; i++) cout << dist[i] << " ";↵
 ↵
}↵
~~~~~↵
↵
I have implemented code for Dijstra ,but it finds only min distance of each node from source node.↵
could anyone please help how to retace the shortest path in this approach .Thank you

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский electro177 2021-06-28 19:08:02 1
en1 Английский electro177 2021-06-28 19:05:49 1113 Initial revision (published)