Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdlib>
- #include <deque>
- using namespace std;
- int main(){
- //set
- int path_len[6][6] = {
- {0, 4, 7, 3, -1, -1},
- {4, 0, 3, -1, 2, -1},
- {7, 3, 0, -1, -1, 2},
- {3, -1, -1, 0, 3, -1},
- {-1, 2, 2, 3, 0, 2},
- {-1, 2, -1, 2, -1, 0}
- };
- int close[6], greedy[6], path[6], flag = 0;
- //clear
- for(int i=0;i<6;i++){
- close[i] = path[i] = 0;
- greedy[i] = path_len[0][i];
- }
- //start Dijkstra
- int T = 6;
- while(T--){
- //find min
- for(int i=0;i<6;i++){
- if(flag == i || close[i]) continue;
- if(path_len[flag][i] > 0 && (greedy[i] <= 0 || path_len[flag][i] + greedy[flag] < greedy[i])){
- greedy[i] = path_len[flag][i] + greedy[flag];
- path[i] = flag;
- }
- }
- close[flag] = 1;
- //set flag
- int min = 1000000000;
- for(int i=0;i<6;i++){
- if(close[i]) continue;
- if(greedy[i] > 0 && greedy[i] < min){
- min = greedy[i];
- flag = i;
- }
- }
- }
- //output min
- cout << greedy[5] <<endl;
- //output path
- deque<int> find_path;
- T = 5;
- while(T){
- find_path.push_front(T);
- T = path[T];
- }
- while(!find_path.empty()){
- cout << find_path.front() << " ";
- find_path.pop_front();
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment