| 4 | using namespace std; |
| 5 | |
| 6 | int main() |
| 7 | { |
| 8 | int n, m, source; |
| 9 | cin >> n >> m; |
| 10 | vector<pair<int, int>> g[n + 1]; // 1-indexed adjacency list for of graph |
| 11 | |
| 12 | int a, b, wt; |
| 13 | for (int i = 0; i < m; i++) |
| 14 | { |
| 15 | cin >> a >> b >> wt; |
| 16 | g[a].push_back(make_pair(b, wt)); |
| 17 | g[b].push_back(make_pair(a, wt)); |
| 18 | } |
| 19 | |
| 20 | cin >> source; |
| 21 | |
| 22 | // Dijkstra's algorithm begins from here |
| 23 | priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // min-heap ; In pair => (dist,from) |
| 24 | vector<int> distance(n + 1, INT_MAX); // 1-indexed array for calculating shortest paths; |
| 25 | |
| 26 | distance[source] = 0; |
| 27 | pq.push(make_pair(0, source)); // (dist,from) |
| 28 | |
| 29 | while (!pq.empty()) |
| 30 | { |
| 31 | int dist = pq.top().first; |
| 32 | int prev = pq.top().second; |
| 33 | pq.pop(); |
| 34 | |
| 35 | vector<pair<int, int>>::iterator it; |
| 36 | for (it = g[prev].begin(); it != g[prev].end(); it++) |
| 37 | { |
| 38 | int next = it->first; |
| 39 | int nextDist = it->second; |
| 40 | if (distance[next] > distance[prev] + nextDist) |
| 41 | { |
| 42 | distance[next] = distance[prev] + nextDist; |
| 43 | pq.push(make_pair(distance[next], next)); |
| 44 | } |
| 45 | } |
| 46 | } |
| 47 | |
| 48 | cout << "The distances from source, " << source << ", are : \n"; |
| 49 | for (int i = 1; i <= n; i++) |
| 50 | cout << distance[i] << " "; |
| 51 | cout << "\n"; |
| 52 | |
| 53 | return 0; |
| 54 | } |