This is the personal work of Denis Dmitriev; it is not an officially verified or endorsed solution.
Denis writes: Actually this problem can be solved in somewhat simpler way (because of the limitations imposed on the road system), but since it's much easier and faster to code just a standard path-finding over the regular graph, this solution is more suitable for a real contest (where time is a precious resource). Effectiveness in this particular case is not of a big concern because the maximum number of vertices (26) is low enough. -DD
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <deque> #include <string> using namespace std; void main(void) { FILE *fp=fopen("rom.in","r"); FILE *fo=fopen("rom.out","w"); char name[16][2]; int b,e,i,j,roads,queries; bool map[26][26]; memset(map,0,sizeof(map)); fscanf(fp,"%d %d",&roads,&queries); /* read the map */ for(i=0;i<roads;i++) { fscanf(fp,"%s %s",name[0],name[1]); /* since all the letters but first may be ignored (remember, * `No * two cities begin with the same letter'), we will ignore * them */ b=*name[0]-'A',e=*name[1]-'A'; map[b][e]=map[e][b]=true; } for(i=0;i<queries;i++) { deque<int> p; string visited[26]; /* read the query */ fscanf(fp,"%s %s",name[0],name[1]); b=*name[0]-'A'; e=*name[1]-'A'; /* initialize deque (depth search) */ p.push_back(b); visited[b]+=*name[0]; /* if there are still vertices in deque... */ while(!p.empty()) { /* take the one in the beginning */ int c=p[0]; p.pop_front(); /* and check if it is possible to make a step from * it * to some other vertex, shortening the route from * the * origin to it */ for(j=0;j<26;j++) { string &v=visited[j]; /* if there is a road and the target city * was * not visited yet or the route through `c' * is * more optimal than the one already * found... */ if(map[c][j]&&(v.empty()||v.size()>visited[c].size()+1)) { /* ...move to it */ v=visited[c],v+='A'+j,p.push_back(j); /* if the destination was * encountered... */ if(j==e) { /* ...forcingly quit the * loop */ p.clear(); break; } } } } /* print the answer */ fprintf(fo,"%s\n",visited[e].c_str()); } fclose(fo); fclose(fp); }