Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2019
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.95 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <string>
  6. #include <map>
  7. #include <set>
  8.  
  9. #define ll long long
  10. #define endl "\n"
  11.  
  12. using namespace std;
  13.  
  14. int main()
  15. {
  16. int n;
  17. cin >> n;
  18. vector<vector<pair<int, ll>>> g(n);
  19. for (int i = 0; i < n; ++i)
  20. {
  21. for (int j = 0; j < n; ++j)
  22. {
  23. ll a;
  24. cin >> a;
  25. if (a != -1)
  26. {
  27. g[i].push_back({ j, a });
  28. }
  29. }
  30. }
  31.  
  32. vector<vector<ll>> dp(n, vector<ll>(n, 2e18));
  33. for (int i = 0; i < n; ++i)
  34. {
  35. for (auto u : g[i])
  36. {
  37. dp[i][u.first] = min(dp[i][u.first], u.second);
  38. }
  39. }
  40. for (int k = 1; k < n; ++k)
  41. {
  42. for (int i = 0; i < n; ++i)
  43. {
  44. for (int j = 0; j < n; ++j)
  45. {
  46. dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
  47. }
  48. }
  49. }
  50. ll ans = -2e18;
  51. for (int i = 0; i < n; ++i)
  52. {
  53. for (int j = 0; j < n; ++j)
  54. {
  55. if (dp[i][j] != 2e18)
  56. {
  57. ans = max(ans, dp[i][j]);
  58. }
  59. }
  60. }
  61.  
  62. cout << ans;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement