Spoj EZDIJKST - Easy Dijkstra Problem Solution

  

  Problem Link: https://www.spoj.com/problems/EZDIJKST/en/ 

Solution in C++:

1. /// La ilaha illellahu muhammadur rasulullah
2. ///******Bismillahir-Rahmanir-Rahim******///
3. /// Abul Hasnat Tonmoy
4. /// Department of CSE,23rd batch
5. /// Islamic University,Bangladesh
6. ///**********ALLAH IS ALMIGHTY************///
7. #include <bits/stdc++.h>
8. using namespace std;
9. const int N = 1e4 + 9;
10. #define infinity 1 << 30 // 2^30
11. struct node {
12. int u;
13. int cost;
14. node(int _u, int _cost) {
15. u = _u;
16. cost = _cost;
17. }
18. bool operator<(const node& p) const { return cost > p.cost; }
19. };
20. void dijstkra(int n, vector<int> g[], vector<int> cost[], int source, int des) {
21. int distance[n + 1];
22. int f = 0;
23. for (int i = 1; i <= n; i++) {
24. distance[i] = infinity;
25. }
26. priority_queue<node> q;
27. q.push(node(source, 0));
28. distance[source] = 0;
29. while (!q.empty()) {
30. node top = q.top();
31. q.pop();
32. int u = top.u;
33. for (int i = 0; i < (int)g[u].size(); i++) {
34. int v = g[u][i];
35. if (distance[u] + cost[u][i] < distance[v]) {
36. distance[v] = distance[u] + cost[u][i];
37. q.push(node(v, distance[v]));
38. if (v == des) f = 1;
39. }
40. }
41. }
42. if (f == 1)
43. cout << distance[des] << endl;
44. else
45. cout << "NO" << endl;
46. }
47. int main() {
48. int t;
49. cin >> t;
50. while (t--) {
51. vector<int> g[N], cost[N];
52. int numNodes, numEdges, des;
53. cin >> numNodes >> numEdges;
54. for (int i = 0; i < numEdges; i++) {
55. int u, v, w;
56. cin >> u >> v >> w;
57. g[u].push_back(v);
58. cost[u].push_back(w);
59. }
60. int source;
61. cin >> source >> des;
62. dijstkra(numNodes, g, cost, source, des);
63. }
64. return 0;
65. }