daily pastebin goal
15%
SHARE
TWEET

Untitled

a guest Feb 17th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #include <queue>
  5. #include <sstream>
  6. #define INF 100000
  7. const int N=24;
  8. using namespace std;
  9.  
  10.  
  11.  
  12. string to_string(int a){
  13.     string tmp;
  14.     stringstream ss;
  15.     ss<<a;
  16.     return ss.str();
  17. }
  18.  
  19. int sortT(int** mas,queue<int>* path,int a,int b){
  20.      queue<int> edges;
  21.      int curr;
  22.      edges.push(a);
  23.      do{
  24.         if(edges.empty()) return -1;
  25.         curr=edges.front();
  26.         edges.pop();
  27.         path->push(curr);
  28.         for(int i=0;i<N;i++) if(mas[curr][i]>0) edges.push(i);
  29.      } while(curr!=b);
  30.         path->push(curr);
  31.      return 0;
  32. }
  33.  
  34. int dyn(int** mas,int a,int b){
  35.     int dist[N];
  36.     queue<int> path;
  37.     int prev[N];
  38.     for(int i=0;i<N;i++) dist[i]=INF;
  39.     dist[a]=0;
  40.     switch(sortT(mas,&path,a,b)){
  41.         case -1:{
  42.             cout<<"ureachable";
  43.             return -1;
  44.             break;
  45.         }
  46.         case -2:{
  47.             cout<<"cycle";
  48.             return -1;
  49.             break;
  50.         }
  51.     }
  52.     int i;
  53.     for(int i;path.empty()==false;path.pop()){
  54.         i=path.front();
  55.         for(int j=0;j<N;j++){
  56.             if(j==i || mas[i][j]<1) continue;
  57.             if(dist[j]>dist[i]+mas[i][j]){
  58.                 dist[j]=dist[i]+mas[i][j];
  59.                 prev[j]=i;
  60.             }
  61.         }
  62.     }
  63.     cout<<"Shortest path value is "<<dist[b]<<endl;
  64.     cout<<"Path:";
  65.     string ResPath="->"+to_string(b);
  66.     for(int i=b;i!=a;i=prev[i]) ResPath="->"+to_string(prev[i])+ResPath;
  67.     ResPath.erase(ResPath.begin(),ResPath.begin()+1);
  68.     cout<<ResPath<<endl;
  69.     return 0;
  70. }
  71.  
  72. void printGraph(int **mas){
  73.     cout<<"   ";
  74.     for(int i=0;i<N;i++) {
  75.         if(i<10) cout<<' ';
  76.         cout<<' '<<i;
  77.     }
  78.     cout<<endl<<"  ";
  79.     for(int i=0;i<N;i++) cout<<"___";
  80.     cout<<endl;
  81.     for(int i=0;i<N;i++){
  82.         if(i<10) cout<<' ';
  83.         cout<<i<<"| "<<mas[i][0];
  84.         for(int j=1;j<N;j++) {
  85.             if(mas[i][j]>9) cout<<' '; else cout<<"  ";
  86.             cout<<mas[i][j];
  87.         }
  88.         cout<<endl;
  89.     }
  90. }
  91.  
  92. void clearGraph(int **mas){
  93.     for(int i=0;i<N;i++) delete [] mas[i];
  94.     delete [] mas;
  95. }
  96.  
  97. int main() {
  98.     int** graph=new int*[N];
  99.     for(int i=0;i<N;i++) graph[i]=new int[N];
  100.     ifstream file("test.txt");
  101.     for(int i=0;i<N;i++)
  102.     for(int j=0;j<N;j++) file>>graph[i][j];
  103.     file.close();
  104.    
  105.     int start,end;
  106.     cout<<"Write start edge:";
  107.     cin>>start;
  108.     cout<<"Write end edge:";
  109.     cin>>end;
  110.     printGraph(graph);
  111.     getchar();
  112.     dyn(graph,start,end);
  113.     clearGraph(graph);
  114.     return 0;
  115. }
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