fork download
copy 
  1. #include<iostream>
  2. #include<fstream>
  3. #include<string>
  4. #include<queue>
  5. #include<stack>
  6. using namespace std;
  7. string city_num[700];
  8. int num_total_city;
  9. bool m[700][700],inside,findend=0;
  10. queue<int> q;
  11. stack<string> p;
  12. int father[700],from_num,to_num;
  13. int searching(string s){
  14.     int i;
  15.     for(i=0;i<num_total_city;i++){
  16.         if(city_num[i]==s){
  17.             return i;
  18.         }
  19.     }
  20.     return -1;
  21. }
  22. void bfs(int i){
  23.     int j;
  24.     if(i<0) return;
  25.     for(j=0;j<num_total_city;j++){
  26.         if(m[i][j]){
  27.             if(father[j]==-1) father[j]=i;
  28.             if(j==to_num){
  29.                 findend=true;
  30.                 return;
  31.             }
  32.             q.push(j);
  33.             m[j][i]=false;
  34.         }
  35.     }
  36.     while(!q.empty()){
  37.         i=q.front();
  38.         for(j=0;j<num_total_city;j++){
  39.             if(m[i][j]){
  40.                 if(father[j]==-1) father[j]=i;
  41.                 if(j==to_num){
  42.                     findend=true;
  43.                     return;
  44.                 }
  45.                 q.push(j);
  46.                 m[j][i]=false;
  47.             }
  48.         }
  49.         q.pop();
  50.     }
  51. }
  52. int main()
  53. {
  54.     ifstream fin;
  55.     fin.open("7.txt");
  56.     istream& input(cin);
  57.  
  58.     int i,j,num1,num2,n;
  59.     string city[1400],from,to;
  60.     char x;
  61.  
  62.     while(input>>n){
  63.         for(i=0;i<700;i++){
  64.             for(j=0;j<700;j++){
  65.                 m[i][j]=false;
  66.             }
  67.         }
  68.         while(!p.empty()) p.pop();
  69.         while(!q.empty()) q.pop();
  70.         findend=false;
  71.         for(i=0;i<700;i++){
  72.             city_num[i]="";
  73.             father[i]=-1;
  74.         }
  75.         for(i=0;i<1400;i++){
  76.             city[i]="";
  77.         }
  78.  
  79.         for(i=0;i<n*2;i++){
  80.             input>>city[i];
  81.         }
  82.         input>>from>>to;
  83.         num_total_city=0;
  84.         for(i=0;i<n*2;i++){
  85.             inside=false;
  86.             for(j=0;j<num_total_city;j++){
  87.                 if(city[i]==city_num[j]){
  88.                     inside=true;
  89.                 }
  90.             }
  91.             if(!inside){
  92.                 city_num[num_total_city]=city[i];
  93.                 num_total_city++;
  94.             }
  95.         }
  96.         for(i=0;i<n*2;i=i+2){
  97.             num1=searching(city[i]);
  98.             num2=searching(city[i+1]);
  99.             m[num1][num2]=true;
  100.             m[num2][num1]=true;
  101.         }
  102.         /*for(i=0;i<num_total_city;i++){
  103.             for(j=0;j<num_total_city;j++){
  104.                 cout<<m[i][j];
  105.             }
  106.             cout<<endl;
  107.         }*/
  108.         from_num=searching(from);
  109.         to_num=searching(to);
  110.         bfs(from_num);
  111.         p.push(to);
  112.         i=to_num;
  113.         while(father[i]!=-1){
  114.             i=father[i];
  115.             p.push(city_num[i]);
  116.         }
  117.         if(!findend&&to!=from){
  118.             cout<<"No route"<<endl;
  119.         }
  120.         if(findend){
  121.             while(!p.empty()){
  122.                 cout<<p.top()<<" ";
  123.                 p.pop();
  124.                 cout<<p.top()<<endl;
  125.                 if(p.size()==1) break;
  126.             }
  127.         }
  128.         cout<<endl;
  129.     }
  130. }
  131.  
Success #stdin #stdout 0s 3968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/P2eUtE
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!