UVA 558 - Wormholes Solution

                             

 

Problem Link  : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=499

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. #define mx 2009
10. #define inf INT_MAX
11. typedef struct {
12. int u, v, w;
13. } Edge;
14. Edge edge[mx];
15. int n, m;
16. int dis[mx];
17. int BellmanFord(int source) {
18. for (int i = 0; i < n; i++) {
19. dis[i] = inf;
20. }
21. dis[source] = 0;
22. for (int i = 0; i < n - 1; i++) {
23. for (int j = 0; j < m; j++) {
24. if (dis[edge[j].v] > dis[edge[j].u] + edge[j].w) {
25. dis[edge[j].v] = dis[edge[j].u] + edge[j].w;
26. }
27. }
28. }
29. for (int j = 0; j < m; j++) {
30. if (dis[edge[j].v] > dis[edge[j].u] + edge[j].w) {
31. return 0;
32. }
33. }
34. return 1;
35. }
36. int32_t main() {
37. int t;
38. cin >> t;
39. while (t--) {
40. cin >> n >> m;
41. for (int i = 0; i < m; i++) {
42. cin >> edge[i].u >> edge[i].v >> edge[i].w;
43. }
44. if (BellmanFord(0)) cout << "not ";
45. cout << "possible" << endl;
46. }
47. return 0;
48. }