~~~~~↵
#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
#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



