UVa 10507 - Waking up brain

分析：搜索，最短路。激活需要的时间就是使每块被激活的时间最短，这些最小值中的最大值。虽然，初始有三个点，可以设一个原始点，进行单元最短路径算法即可；而且，由于节点间的路径长度相同，利用bfs即可。这里利用maps记录连接关系和激活关系（值为0不连通，值为1连通未激活，值为2为连通激活）。每次找到未激活节点中连接激活边大于3条的放入队列（激活）即可，因为此时一定是最早的激活时间。最后，记录最大的激活时间和判断是否所有节点都激活即可。

注意：输入和输出格式。

#include   
#include   
#include   
  
using namespace std;  
  
int maps[30][30];  
int queue[30];  
int head,tail;  
int times[30];  
int wake[30];  
//初始化   
void init()  
{  
    for ( int i = 0 ; i < 26 ; ++ i )  
    for ( int j = 0 ; j < 26 ; ++ j )  
        maps[i][j] = maps[j][i] = 0;  
    for ( int i = 0 ; i < 26 ; ++ i )  
        wake[i] = 0;  
    head = tail = 0;  
}  
//入队   
void push( int id, int t )  
{  
    queue[tail ++] = id;  
    times[id] = t;  
    wake[id] = 1;  
}  
//搜索   
void bfs( int n )  
{  
    int max_time = 0;  
    while ( head < tail ) {  
        int id = queue[head ++];  
        int  t = times[id];  
        //更新连接边的激活属性   
        for ( int i = 0 ; i < 26 ; ++ i )  
            if ( maps[id][i] )  
                maps[id][i] = maps[i][id] = 2;  
        //判断未激活节点相连的激活边是否大于 3   
        for ( int i = 0 ; i < 26 ; ++ i )   
            if ( !wake[i] ) {  
                int sum = 0;  
                for ( int j = 0 ; j < 26 ; ++ j )  
                    if ( i != j && maps[i][j] >





 1 )  
                        sum ++;  
                if ( sum >= 3 ) {  
                    push( i, t+1 );  
                    if ( max_time < t+1 )  
                        max_time = t+1;  
                }  
            }  
    }  
      
    int sum = 0;  
    for ( int i = 0 ; i < 26 ; ++ i )  
        if ( wake[i] )   
            sum ++;  
    if ( sum != n )  
        printf("THIS BRAIN NEVER WAKES UP\n");  
    else printf("WAKE UP IN, %d, YEARS\n",max_time);  
}  
  
int main()  
{  
    int  N,M;  
    char A,B,C;  
    while ( ~scanf("%d",&N) ) {  
        getchar();  
        scanf("%d",&M);  
        getchar();  
        scanf("%c%c%c",&A,&B,&C);  
        getchar();  
          
        init();  
        push( A-'A', 0 );  
        push( B-'A', 0 );  
        push( C-'A', 0 );  
          
        for ( int i = 0 ; i < M ; ++ i ) {  
            scanf("%c%c",&A,&B);  
            getchar();  
            maps[A-'A'][B-'A'] = 1;  
            maps[B-'A'][A-'A'] = 1;  
        }  
          
        bfs( N );  
    }  
    return 0;     
}