daily pastebin goal
56%
SHARE
TWEET

Untitled

a guest Jan 17th, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.         #include <cstdlib>
  3.         #include <deque>
  4.          
  5.         using namespace std;
  6.          
  7.         int main(){
  8.                 //set
  9.                 int path_len[6][6] = {
  10.                         {0, 4, 7, 3, -1, -1},
  11.                         {4, 0, 3, -1, 2, -1},
  12.                         {7, 3, 0, -1, -1, 2},
  13.                         {3, -1, -1, 0, 3, -1},
  14.                         {-1, 2, 2, 3, 0, 2},
  15.                         {-1, 2, -1, 2, -1, 0}
  16.                 };
  17.                 int close[6], greedy[6], path[6], flag = 0;
  18.                
  19.                 //clear
  20.                 for(int i=0;i<6;i++){
  21.                         close[i] = path[i] = 0;
  22.                         greedy[i] = path_len[0][i];
  23.                 }
  24.                
  25.                 //start Dijkstra
  26.                 int T = 6;
  27.                 while(T--){
  28.                         //find min
  29.                         for(int i=0;i<6;i++){
  30.                                 if(flag == i || close[i])       continue;
  31.                                
  32.                                 if(path_len[flag][i] > 0 && (greedy[i] <= 0 || path_len[flag][i] + greedy[flag] < greedy[i])){
  33.                                         greedy[i] = path_len[flag][i] + greedy[flag];
  34.                                         path[i] = flag;
  35.                                 }
  36.                         }
  37.                         close[flag] = 1;
  38.                         //set flag
  39.                         int min = 1000000000;
  40.                         for(int i=0;i<6;i++){
  41.                                 if(close[i]) continue;
  42.                                 if(greedy[i] > 0 && greedy[i] < min){
  43.                                         min = greedy[i];
  44.                                         flag = i;
  45.                                 }
  46.                         }
  47.                 }
  48.                 //output min
  49.                 cout << greedy[5] <<endl;
  50.                 //output path
  51.                 deque<int> find_path;
  52.                 T = 5;
  53.                 while(T){
  54.                         find_path.push_front(T);
  55.                         T = path[T];
  56.                 }
  57.                 while(!find_path.empty()){
  58.                         cout << find_path.front() << " ";
  59.                         find_path.pop_front();
  60.                 }
  61.                 return 0;
  62.         }
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