ACM UVA-627

這題用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");
}