#include <stdio.h>#include <memory.h>int city;char graph [26][26];char fortify [26];int Dijkstra(){int i, j, k;int searched [26];int hop [26];for ( i = 0; i < city; i ++ )if ( fortify [i] ) hop [i] = 0;else hop [i] = 100;memset(searched, 0, sizeof(searched));for ( i = 0; i < city; i ++ ) {k = -1;for ( j = 0; j < city; j ++ )if ( !searched [j] ) if ( k < 0 || hop [j] < hop [k] ) k = j;if ( k < 0 ) break;searched [k] = 1;for ( j = 0; j < city; j ++ )if (!searched [j])if ( graph [k][j] && hop [k] + 1 < hop [j] )hop [j] = hop [k] + 1;}j = -1;for ( i = 0; i < city; i ++ )if ( !fortify [i] )if ( j < 0 || hop [j] < hop [i] ) j = i;fortify [j] = 1;return j;}int main (){int i;int total;char first, str[10];char a , b;scanf("%d%s%dn", &city, str, &total);first = str[0];memset (fortify, 0, sizeof(fortify));memset (graph, 0, sizeof(graph));for ( i = 1; i < city; i ++ ) {scanf("%c %cn", &a, &b);graph[a-'A'][b-'A'] = 1;graph[b-'A'][a-'A'] = 1;}fortify [first - 'A'] = 1;printf("Program 8 by team Xn");printf("%c", first);for (i = 1; i < total; i ++ )printf(" %c", Dijkstra() + 'A');printf("n");printf("End of program 8 by team Xn");return 0;}
