Advertisement
Guest User

Untitled

a guest
Dec 15th, 2018
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.04 KB | None | 0 0
  1.  
  2.  
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. #define int long long
  9.  
  10. vector<vector<pair<int, int>>> g;
  11.  
  12. const int inf = 1e12;
  13.  
  14. main()
  15. {
  16. #ifdef _DEBUG
  17. freopen("in.txt","rt",stdin);
  18. #endif // _DEBUG
  19.  
  20. int n, s, f;
  21. cin >> n >> s >> f;
  22. s--, f--;
  23.  
  24. g.resize(n);
  25. for (int i = 0; i < n; i++)
  26. {
  27. for (int j = 0; j < n; j++)
  28. {
  29. int t;
  30. scanf("%lld", &t);
  31.  
  32. if (t != -1 && (i != j))
  33. g[i].push_back({j, t});
  34. }
  35. }
  36.  
  37. vector<bool> used(n, false);
  38. vector<int> d(n, inf);
  39. d[s] = 0;
  40.  
  41. for (int i = 0; i < n; i++)
  42. {
  43. int v = -1;
  44. for (int j = 0; j < n; j++)
  45. if (!used[j] && (v == -1 || d[j] < d[v]))
  46. v = j;
  47.  
  48. if (d[v] == inf)
  49. break;
  50. used[v] = true;
  51.  
  52.  
  53. for (int j = 0; j < g[v].size(); j++)
  54. {
  55. int to = g[v][j].first;
  56. int len = g[v][j].second;
  57.  
  58. if (d[v] + len < d[to])
  59. d[to] = d[v] + len;
  60. }
  61. }
  62.  
  63. if (d[f] == inf)
  64. cout << -1;
  65. else
  66. cout << d[f];
  67.  
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement