Advertisement
Guest User

Untitled

a guest
Dec 18th, 2018
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.08 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <string>
  6. #include <math.h>
  7. #include <climits>
  8.  
  9. #define ll long long
  10. using namespace std;
  11. //freopen("a.in", "r", stdin);
  12. //freopen("a.out", "w", stdout);
  13.  
  14. int a[2001][2001];
  15. ll used[2001];
  16. int n, s, t, x;
  17.  
  18. ll xtofs(int v){
  19. if(v == s)
  20. return 0;
  21. ll m = LLONG_MAX;
  22. ll h;
  23. for(int i = 0; i < n; i++){
  24. if(a[v][i] > 0){
  25. if(used[i] == LLONG_MAX){
  26. h = xtofs(i);
  27. }else{
  28. h = used[i];
  29. }
  30. if(h != LLONG_MAX)
  31. m = min(m, h + a[v][i]);
  32. }
  33. }
  34. used[v] = m;
  35. return m;
  36. }
  37.  
  38. int main()
  39. {
  40. ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  41. cin >> n >> s >> t;
  42. fill(used, used + 2001, LLONG_MAX);
  43. s--;
  44. t--;
  45. for(int i = 0; i < n; i++){
  46. for(int j = 0; j < n; j++){
  47. cin >> x;
  48. a[j][i] = x;
  49. }
  50. }
  51. ll q = xtofs(t);
  52. if(q == LLONG_MAX)
  53. cout << -1;
  54. else
  55. cout << q;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement