all roads lead where.txt

来自「以前ACM在哈工程HRBEU做的一些简单题目」· 文本 代码 · 共 63 行

#include<stdio.h>
int map[30][30], path[30][30];
char city[30];
int c_t = 0;
int TransformNum(char *s)
{
   int i;
   for(i=0; i<=c_t; ++i)
       if( city[i]==s[0] ) return i;
   city[c_t++]=s[0];
   return c_t-1;
}
void Floyd()
{
   for(int k=0; k<c_t; ++k)
       for(int i=0; i<c_t; ++i)
           for(int j=0; j<c_t; ++j)
               if( map[i][j] > map[i][k] + map[k][j] ) {
                   map[i][j] = map[i][k] + map[k][j];
                   path[i][j] = path[k][j];
               }
}
void initial()
{
   c_t = 0;
   for(int i=0; i<30; ++i) {
       for(int j=0; j<30; ++j) {
           if( i != j ) map[i][j] = 32767;
           else map[i][j] = 0;
           path[i][j] = i;
       }
   }
}
void PrintPath(int s, int d)
{
   if( s != d ) PrintPath(s, path[s][d]);
   printf("%c",city[d]);
}
int main(void)
{
   int T, m, n, s, d;
   char citya[30], cityb[30];
    initial();
    scanf("%d%d",&m,&n);
       for(; m>0; --m) 
       {
           scanf("%s%s",citya,cityb);
           s = TransformNum(citya);
           d = TransformNum(cityb);
           map[s][d] = map[d][s] = 1;
       }
       Floyd();
       for(; n>0; --n) {
           scanf("%s%s",citya,cityb);
           s = TransformNum(citya);
           d = TransformNum(cityb);
           PrintPath(s,d);
           printf("\n");
       }
   
   return 0;
}