Advertisement
Guest User

Untitled

a guest
Feb 27th, 2020
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.37 KB | None | 0 0
  1. #include <fstream>
  2. #include <iostream>
  3. #include <queue>
  4. #include <set>
  5. #include <sstream>
  6. #include <string>
  7. #include <vector>
  8.  
  9.  
  10. #define MAX(a, b) ((a) > (b) ? (a) : (b))
  11. #define MIN(a, b) ((a) < (b) ? (a) : (b))
  12. #define __PAUSE system("pause");
  13. #define VEC std::vector <
  14. #define QUE std::queue <
  15. #define SET std::set <
  16. #define PAIR std::pair <
  17. #define in std::cin
  18. #define out std::cout
  19.  
  20. typedef long long ll;
  21. /*
  22. struct set_struct {
  23. ll marked = 0;
  24. ll set_vertex;
  25. }; // set data
  26. */
  27. struct list_struct {
  28. ll vertex;
  29. ll len_to_v;
  30. }; // list data
  31.  
  32. VEC VEC list_struct >> gr;
  33. VEC ll > dist;
  34. ll n, m;
  35.  
  36. int main() {
  37. ll start, f;
  38. in >> n >> start >> f;
  39. start--;
  40. f--;
  41. gr.resize(n);
  42. dist.resize(n, 1e9);
  43. for (ll i = 0; i < n; i++) {
  44. for (ll j = 0; j < n; j++) {
  45. static ll x;
  46. in >> x;
  47. if (x != -1) gr[i].push_back({j, x});
  48. }
  49. }
  50. dist[start] = 0;
  51. SET PAIR ll, ll>> s;
  52. s.insert({0, start});
  53. while (!s.empty()) {
  54. ll v = s.begin()->second;
  55. s.erase(s.begin());
  56. for (auto p : gr[v]) {
  57. ll u = p.vertex, w = p.len_to_v;
  58. if (dist[u] > dist[v] + w) {
  59. s.erase({dist[u], u});
  60. dist[u] = dist[v] + w;
  61. s.insert({dist[u], u});
  62. }
  63. }
  64. }
  65. if (dist[f] == 1e9) {
  66. out << -1;
  67. __PAUSE
  68. return 0;
  69. }
  70. out << dist[f] << "\n";
  71. __PAUSE
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement