PersonalCorpus 版 (精华区)

904456 2002/06/15 10:58:33.654
Big Guava ... 762 C++ Accepted 0:00.040 64

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>


void main()
{
#ifndef ONLINE_JUDGE
    freopen("c:\\uva\\input762.txt","r",stdin);
    freopen("c:\\uva\\output762.txt","w",stdout);
#endif

    char dl[676][676];
    char used[676];
    int i,j,k,n,end,fin;
    char s[100];
    int path[1000],from[1000],res[1000];

    while (scanf("%d\n",&n)==1) {
        memset(dl,0,sizeof(dl));
        memset(used,0,sizeof(used));
        for (i=0;i<n;i++) {
            gets(s);
            j=(s[0]-'A')*26+s[1]-'A';
            k=(s[3]-'A')*26+s[4]-'A';
            dl[j][k]=1;
            dl[k][j]=1;
            used[j]=1;
            used[k]=1;
        }
        gets(s);
        j=(s[0]-'A')*26+s[1]-'A';
        end=(s[3]-'A')*26+s[4]-'A';
        path[0]=j; from[0]=-1; used[j]=0;
        i=0;j=1; fin=0;
        while(i<j) {
            for (k=0;k<676;k++) if ((dl[path[i]][k]==1)&&(used[k]==1)) 
{
                path[j]=k;
                from[j]=i;
                if (k==end) { fin=1; break; }
                used[k]=0;
                dl[path[i]][k]=0;
                dl[k][path[i]]=0;
                j++;
            }
            if (fin==1) break;
            i++;
        }
        if (fin==0) printf("No route\n"); else {
            k=0;
            while (j!=-1) {
                res[k]=path[j];
                k++;
                j=from[j];
            }
            for (i=k-1;i>0;i--) printf("%c%c %c%c\n",'A'+res[i]/26,
'A'+res[i]%26,
                                'A'+res[i-1]/26,'A'+res[i-1]%26);
        }
        if (gets(s)!=NULL) printf("\n");
    }
}