![:(](./images/smilies/icon_frown.gif)
here is my code
Code: Select all
#pragma warning ( disable : 4786 )
#include<stdio.h>
#include<vector>
#include<queue>
#include<string>
#include<vector>
#include<iostream>
using namespace std;
#define max 5000
vector<string> K(100000);
bool adj[max][max],T[max];
int node,D[max],H[max];
void Ini(string s){
int i;
for(i=0;i<node;i++)
if(K[i]==s) return;
K[node++]=s;
return;
}
int hash(string s){
int i;
for(i=0;i<node;i++)
if(K[i]==s)return i;
return i;
}
void bfs(string s,string d){
int i,j,k,b=0;
i=hash(s);
j=hash(d);
queue<int> Q;
Q.push(i);
D[i]=0;
T[i]=false;
while(!Q.empty()){
k=Q.front();
Q.pop();
for(i=0;i<node;i++)
if(adj[k][i]&&T[i]){
D[i]=k;
T[i]=false;
Q.push(i);
if(i==j){b=1;break;}
}
if(b==1)break;
}
i=0;
k=0;
if(b==1){
while(1){
H[k++]=j;
j=D[j];
if(j==i)break;
}
for(i=k-1;i>=0;i--){
cout<<K[D[H[i]]]<<" "<<K[H[i]];
printf("\n");
}
}
if(b==0) printf("No route\n");
}
int main(){
char x[10],y[10];
int i,j,g,z;
string s,v;
bool u=false;
while(scanf("%d",&g)!=EOF){
node=0;
if(u)printf("\n");
memset(adj,false,sizeof(adj));
memset(D,0,sizeof(D));
memset(T,true,sizeof(T));
for(z=0;z<g;z++){
scanf("%s %s",x,y);
s=x;
v=y;
Ini(s);
Ini(v);
i=hash(s);
j=hash(v);
adj[i][j]=true;
adj[j][i]=true;
}
scanf("%s %s",x,y);
s=x;
v=y;
bfs(s,v);
u=true;
}
return 0;
}