Advertisement
StoneHaos

mod_n7_v12

Jan 28th, 2022
1,147
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. const int n = 10;
  9.  
  10. int mtx[n][n] = {
  11.     {0, 0, 3, 2, 0, 0, 0, 0, 0, 0},
  12.     {0, 0, 4, 2, 1, 0, 0, 0, 0, 0},
  13.     {0, 0, 0, 0, 0, 4, 0, 2, 0, 0},
  14.     {0, 0, 0, 0, 0, 4, 0, 2, 5, 0},
  15.     {0, 0, 0, 0, 0, 0, 2, 4, 0, 0},
  16.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 3},
  17.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 4},
  18.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 2},
  19.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 3},
  20. };
  21. int dp1[n];
  22. int dp2[n];
  23.  
  24. int main() {
  25.     dp1[0] = 0;
  26.     dp2[1] = 0;
  27.     for (int i = 2; i < n; ++ i) {
  28.         int mn = 10000;
  29.         for (int j = i - 1; j >= 0; -- j) {
  30.             if (mtx[j][i] != 0 && j != 1)
  31.                 mn = min(mn, dp1[j] + mtx[j][i]);
  32.         }
  33.         dp1[i] = mn;
  34.     }
  35.     int x = n - 1;
  36.     vector<int> v;
  37.     v.push_back(x);
  38.     while (x != 0) {
  39.         //printf("%d\n", x);
  40.         for (int i = 0; i < n; ++ i) {
  41.             if (dp1[x] == dp1[i] + mtx[i][x]) {
  42.                 x = i;
  43.                 break;
  44.             }
  45.         }
  46.         v.push_back(x);
  47.     }
  48.     printf("1:\n");
  49.     printf("dp:");
  50.     for (int i = 0; i < n; ++ i)
  51.         printf(" %d", dp1[i]);
  52.     printf("\n");
  53.     reverse(v.begin(), v.end());
  54.     printf("way:");
  55.     for (int i = 0; i < v.size(); ++ i) {
  56.         printf(" %d", v[i] + 1);
  57.     }
  58.     printf("\n\n");
  59.  
  60.  
  61.     for (int i = 2; i < n; ++ i) {
  62.         int mn = 10000;
  63.         for (int j = i - 1; j > 0; -- j) {
  64.             if (mtx[j][i] != 0)
  65.                 mn = min(mn, dp2[j] + mtx[j][i]);
  66.         }
  67.         dp2[i] = mn;
  68.     }
  69.     x = n - 1;
  70.     v.clear();
  71.     v.push_back(x);
  72.     while (x != 1) {
  73.         for (int i = 1; i < n; ++ i) {
  74.             if (dp2[x] == dp2[i] + mtx[i][x]) {
  75.                 x = i;
  76.                 break;
  77.             }
  78.         }
  79.         v.push_back(x);
  80.     }
  81.     printf("2:\n");
  82.     printf("dp:");
  83.     for (int i = 0; i < n; ++ i)
  84.         printf(" %d", dp2[i]);
  85.     printf("\n");
  86.     reverse(v.begin(), v.end());
  87.     printf("way:");
  88.     for (int i = 0; i < v.size(); ++ i) {
  89.         printf(" %d", v[i] + 1);
  90.     }
  91.     printf("\n");
  92.     return 0;
  93. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement