Advertisement
ke_timofeeva7

алхимия

Nov 5th, 2021
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.04 KB | None | 0 0
  1. /*
  2. ⠸⣷⣦⠤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣠⣤⠀⠀⠀
  3. ⠀⠙⣿⡄⠈⠑⢄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠔⠊⠉⣿⡿⠁⠀⠀⠀
  4. ⠀⠀⠈⠣⡀⠀⠀⠑⢄⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠊⠁⠀⠀⣰⠟⠀⠀⠀⣀⣀
  5. ⠀⠀⠀⠀⠈⠢⣄⠀⡈⠒⠊⠉⠁⠀⠈⠉⠑⠚⠀⠀⣀⠔⢊⣠⠤⠒⠊⠉⡜
  6. ⠀⠀⠀⠀⠀⠀⠀⡽⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠩⡔⠊⠁⠀⠀⠀⠀⠀ ⠀⠇
  7. ⠀⠀⠀⠀⠀⠀⠀⡇⢠⡤⢄⠀⠀⠀⠀⠀⡠⢤⣄⠀⡇⠀⠀⠀⠀⠀⠀⠀ ⢰⠀
  8. ⠀⠀⠀⠀⠀⠀⢀⠇⠹⠿⠟⠀⠀⠤⠀⠀⠻⠿⠟⠀⣇⠀⠀⡀⠠⠄⠒⠊⠁⠀
  9. ⠀⠀⠀⠀⠀⠀⢸⣿⣿⡆⠀⠰⠤⠖⠦⠴⠀⢀⣶⣿⣿⠀⠙⢄⠀⠀⠀⠀⠀⠀
  10. ⠀⠀⠀⠀⠀⠀⠀⢻⣿⠃⠀⠀⠀⠀⠀⠀⠀⠈⠿⡿⠛⢄⠀⠀⠱⣄⠀⠀⠀⠀
  11. ⠀⠀⠀⠀⠀⠀⠀⢸⠈⠓⠦⠀⣀⣀⣀⠀⡠⠴⠊⠹⡞⣁⠤⠒⠉⠀⠀⠀⠀⠀
  12. ⠀⠀⠀⠀⠀⠀⣠⠃⠀⠀⠀⠀⡌⠉⠉⡤⠀⠀⠀⠀⢻⠿⠆⠀⠀⠀⠀⠀⠀⠀
  13. ⠀⠀⠀⠀⠀⠰⠁⡀⠀⠀⠀⠀⢸⠀⢰⠃⠀⠀⠀⢠⠀⢣⠀⠀⠀⠀⠀⠀⠀⠀
  14. ⠀⠀⠀⢶⣗⠧⡀⢳⠀⠀⠀⠀⢸⣀⣸⠀⠀⠀⢀⡜⠀⣸⢤⣶⠀⠀⠀⠀⠀⠀
  15. ⠀⠀⠀⠈⠻⣿⣦⣈⣧⡀⠀⠀⢸⣿⣿⠀⠀⢀⣼⡀⣨⣿⡿⠁⠀⠀⠀⠀⠀⠀
  16. ⠀⠀⠀⠀⠀⠈⠻⠿⠿⠓⠄⠤⠘⠉⠙⠤⢀⠾⠿⣿⠟⠋
  17. */
  18.  
  19.  
  20. #include <iostream>
  21. #include <string>
  22. #include <sstream>
  23. #include <vector>
  24. #include <cmath>
  25. #include <algorithm>
  26. #include <memory.h>
  27. #include <stdio.h>
  28. #include <stack>
  29. #include <deque>
  30. #include <queue>
  31. #include <set>
  32. #include <iterator>
  33. #include <map>
  34. #include <iomanip>
  35. #include <unordered_set>
  36. #define int long long
  37. #define pb push_back
  38. #define double long double
  39. #define endl "\n"
  40. #define fir first
  41. #define sec second
  42. #define un unsigned
  43. #define INF 1000000009
  44. #define pii pair<int, int>
  45. #define all(v) v.begin(), v.end()
  46. using namespace std;
  47.  
  48. const int N = 1000009;
  49.  
  50.  
  51. signed main()
  52. {
  53.     ios_base::sync_with_stdio(false);
  54.     cin.tie(0);
  55.     cout.tie(0);
  56.  
  57.     int n, s, f;
  58.     cin >> n >> s >> f;
  59.  
  60.     vector<vector<pii>> gr(n + 1);
  61.    
  62.     for (int i = 0; i < n; i++)
  63.     {
  64.         for (int j = 0; j < n; j++)
  65.         {
  66.             int a;
  67.             cin >> a;
  68.  
  69.             if (a != -1)
  70.             {
  71.                 gr[i + 1].push_back({ j + 1, a });
  72.             }
  73.         }
  74.     }
  75.  
  76.     vector<int> dist(n + 1, INF);
  77.  
  78.     dist[s] = 0;
  79.  
  80.     set<pii> q;
  81.     q.insert({ dist[s], s });
  82.  
  83.     while (!q.empty())
  84.     {
  85.         int v = (*q.begin()).second;
  86.         q.erase(q.begin());
  87.  
  88.         for (int i = 0; i < gr[v].size(); i++)
  89.         {
  90.             int to = gr[v][i].first;
  91.             int len = gr[v][i].second;
  92.  
  93.             if (dist[v] + len < dist[to])
  94.             {
  95.                 q.erase({ dist[to],to });
  96.                 dist[to] = dist[v] + len;
  97.                 q.insert({ dist[to],to });
  98.             }
  99.         }
  100.     }
  101.  
  102.     if (dist[f] == INF)
  103.     {
  104.         cout << -1;
  105.     }
  106.     else
  107.     {
  108.         cout << dist[f];
  109.     }
  110.  
  111.     return 0;
  112. }
  113.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement