Guest User

Untitled

a guest
Sep 11th, 2019
99
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <utility>
  10. #include <cstring>
  11. #include <cassert>
  12. #include <cmath>
  13. #include <stack>
  14. #include <queue>
  15. #include<complex>
  16.  
  17. using namespace std;
  18.  
  19. const int inf = 1e9;
  20.  
  21. int main() {
  22. int n, m;
  23. cin >> n;
  24.  
  25. vector < vector < int > > g(n, vector < int >(n, 0));
  26.  
  27. for (int i = 0; i < n; i++) {
  28. for (int j = 0; j < n; j++) {
  29. cin >> g[i][j];
  30. }
  31. }
  32.  
  33. int start, finish;
  34. cin >> start >> finish;
  35. start--;
  36. finish--;
  37. vector < int > dist(n, inf);
  38. dist[start] = 0;
  39.  
  40. int min_dist = 0;
  41. int min_v = start;
  42.  
  43. vector < bool > used(n, false);
  44. vector < int > prev(n, -1);
  45.  
  46. while (min_dist < inf) {
  47. int v = min_v;
  48. used[v] = true;
  49.  
  50. for (int i = 0; i < g[v].size(); i++) {
  51. int x = i;
  52. if (i == v || g[v][i] == 0) {
  53. continue;
  54. }
  55. int cost = g[v][i];
  56. if (dist[v] + cost < dist[x]) {
  57. prev[x] = v;
  58. dist[x] = dist[v] + cost;
  59. }
  60. }
  61.  
  62. min_dist = inf;
  63.  
  64. for (int i = 0; i < n; i++) {
  65. if (!used[i] && dist[i] < min_dist) {
  66. min_dist = dist[i];
  67. min_v = i;
  68. }
  69. }
  70. }
  71. cout << dist[finish] << endl;
  72.  
  73. vector < int > ans;
  74. int t = finish;
  75. while (prev[t] != -1) {
  76. ans.push_back(t);
  77. t = prev[t];
  78. }
  79. cout << start + 1 << " ";
  80. reverse(ans.begin(), ans.end());
  81. for (int i = 0; i < ans.size(); i++) {
  82. cout << ans[i] + 1 << " ";
  83. }
  84. system("pause");
  85. }
RAW Paste Data