這題用BFS即可解出,有一點必須要注意的是,雖然題目要求當經過的routers數量相同,則輸出最小的id,但因為題目的input已經有幫我們做好排序,所以每次找到的自然都會是最小的id。
//ignore header files
bool bfs(int*,int,int,vector<int>*);
void print_path(int *,int ,int);
int main(int argc, char const* argv[])
{
int n;
char line[1005];
while(scanf("%d",&n) != EOF){
getchar();
vector <int> list[305];
for(int i = 0;i<n;i++){
gets(line);
char *pch = strtok(line,"-, ");
int id = atoi(pch);
pch = strtok(NULL,"-, ");
while(pch != NULL){
int see = atoi(pch);
list[id].push_back(see);
pch = strtok(NULL,"-, ");
}
}
int m;
scanf("%d",&m);
printf("-----\n");
while(m--){
int start,dest;
scanf("%d %d",&start,&dest);
int parent[305] = {0};
bool find = bfs(parent,start,dest,list);
if(find){
print_path(parent,start,dest);
}
else {
printf("connection impossible\n");
}
}
}
return 0;
}
bool bfs(int *parent,const int start,const int dest,vector<int>* list){
queue<int> q;
q.push(start);
bool visit[305] = {0};
while(!q.empty()){
int a = q.front();
q.pop();
for(int i = 0;i<list[a].size();i++){
int b = list[a][i];
if(!visit[b]){
//printf("b = %d,a = %d,dest = %d\n",b,a,dest);
parent[b] = a;
//printf("%d\n",parent[b]);
q.push(b);
visit[b] = 1;
if(b == dest){
return true;
}
}
}
}
return false;
}
void print_path(int *parent,int start,int dest){
int a = dest;
//printf("a = %d\n",a);
//printf("p = %d\n",parent[a]);
stack<int> list;
while(a != start){
list.push(a);
a = parent[a];
}
//list.push_back(start);
printf("%d",start);
while(!list.empty()){
int b = list.top();
list.pop();
printf(" %d",b);
}
printf("\n");
}