Advertisement
Guest User

Untitled

a guest
Apr 28th, 2017
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.30 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cstdio>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. const int MAX = 2005;
  10. const long long INF = 9223372036854775807;
  11.  
  12. int n, m, start, finish, v;
  13. long long w[MAX][MAX], d[MAX];
  14. bool used[MAX];
  15.  
  16. void initialize(){
  17. for(int i = 0; i < n; i++)
  18. d[i] = INF;
  19. }
  20.  
  21. int nextVertex(){
  22. int minV = -1;
  23. for(int i = 0; i < n; i++)
  24. if(!used[i] && (minV == -1 || d[i] < d[minV]))
  25. minV = i;
  26.  
  27. return minV;
  28. }
  29.  
  30. void dijkstra(int s){
  31.  
  32. initialize();
  33. d[start] = 0;
  34.  
  35. while((v = nextVertex()) != -1){
  36. used[v] = true;
  37.  
  38. for(int i = 0; i < n; i++){
  39. long e = w[v][i];
  40.  
  41. if(e == -1 || i == v)
  42. continue;
  43.  
  44. if(d[i] > d[v] + e)
  45. d[i] = d[v] + e;
  46.  
  47. }
  48. }
  49. }
  50.  
  51. int main()
  52. {
  53. freopen ("pathmgep.in", "r", stdin);
  54. freopen ("pathmgep.out" ,"w", stdout);
  55.  
  56. scanf("%d%d%d", &n, &start, &finish);
  57. start--, finish--;
  58.  
  59. for(int i = 0; i < n; i++)
  60. for(int j = 0; j < n; j++)
  61. scanf("%d", &w[i][j]);
  62.  
  63. dijkstra(start);
  64.  
  65. if(d[finish] == INF)
  66. cout << "-1" << endl;
  67. else
  68. cout << d[finish] << endl;;
  69.  
  70. return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement