Denis' Solution 2B: All Roads Lead Where?

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


C++ Source Code

#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);
}