SHARE
TWEET

Untitled

a guest Sep 11th, 2019 96 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top