SHARE
TWEET

Untitled

a guest Feb 27th, 2020 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top