Advertisement
StoneHaos

7

Nov 18th, 2021
1,046
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <limits.h>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. int array[13][13] = {
  9.     {0, 4, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  10.     {0, 0, 0, 7, 8, 11, 0, 0, 0, 0, 0, 0, 0},
  11.     {0, 0, 0, 0, 6, 2, 5, 0, 0, 0, 0, 0, 0},
  12.     {0, 0, 0, 0, 0, 0, 0, 6, 10, 0, 0, 0, 0},
  13.     {0, 0, 0, 0, 0, 0, 0, 8, 9, 0, 0, 0, 0},
  14.     {0, 0, 0, 0, 0, 0, 0, 0, 11, 6, 0, 0, 0},
  15.     {0, 0, 0, 0, 0, 0, 0, 0, 8, 12, 0, 0, 0},
  16.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 10, 0},
  17.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 9, 0},
  18.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 7, 0},
  19.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7},
  20.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8},
  21.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
  22. };
  23. int dynamic[13];
  24.  
  25. int main(void) {
  26.     for (int i = 1; i < 13; ++ i) {
  27.         for (int j = 0; j < 13; ++ j) {
  28.             if (array[j][i] != 0) {
  29.                 if (dynamic[i] == 0) {
  30.                     dynamic[i] = dynamic[j] + array[j][i];
  31.                 }
  32.                 else {
  33.                     dynamic[i] = min(dynamic[j] + array[j][i], dynamic[i]);
  34.                 }
  35.             }
  36.         }
  37.     }
  38.    
  39.     vector<int> back;
  40.     int x = 12;
  41.  
  42.     while (x != 0) {
  43.         for (int i = x; i >= 0; -- i) {
  44.             if (array[i][x] != 0 && dynamic[x] == dynamic[i] + array[i][x]) {
  45.                 back.push_back(x + 1);
  46.                 x = i;
  47.             }
  48.         }
  49.     }
  50.     back.push_back(1);
  51.     reverse(back.begin(), back.end());
  52.     for (int i = 0; i < back.size(); ++ i) {
  53.         cout << back[i] << " ";
  54.     }
  55.     cout << endl;
  56.     cout << dynamic[12] << endl;
  57.     return 0;
  58. }
Advertisement
RAW Paste Data Copied
Advertisement