团体程序设计天梯赛-练习集 - L3-014 周游世界（30 分）

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
constintmaxn=1e4+10;
intd, id;
intminCnt, minTran;
intvis[maxn];
unordered_map<int,int>line;
vector<int>tpath, path, v[maxn];
intfhash(intid1,intid2)
{
returnid1*10000+id2;
}
intcalTran()
{
intpreline=0, cnt=-1;
for(inti=1;i<tpath.size();i++)
    {
id=fhash(tpath[i-1],tpath[i]);
if(line[id]!=preline) cnt++, preline=line[id];
    }
returncnt;
}
voiddfs(ints, intcnt)
{
if(s==d&& (cnt<minCnt||cnt==minCnt&&calTran()<minTran))
    {
path=tpath;
minCnt=cnt;
minTran=calTran();
    }
if(s==d) return;
for(inti=0;i<v[s].size();i++)
    {
inttid=v[s][i]; // 去掉 int dfs最终答案会出问题，因为当 tid 作为全局变量时，一直在变，而局部变量对dfs的一个很大的作用就是每次回溯时，该变量的值可以恢复到起初的值if(!vis[tid])
        {
vis[tid]=1;
tpath.push_back(tid);
dfs(tid, cnt+1);
vis[tid]=0;
tpath.pop_back();
        }
    }
}
intmain()
{
intn,m,pre,q,s;
scanf("%d",&n);
for(inti=1;i<=n;i++)
    {
scanf("%d%d",&m,&pre);
for(intj=1;j<m;j++)
        {
scanf("%d",&id);
v[pre].push_back(id);
v[id].push_back(pre);
line[fhash(pre,id)]=line[fhash(id,pre)]=i;
pre=id;
        }
    }
scanf("%d",&q);
while(q--)
    {
scanf("%d%d",&s,&d);
//        if(!book[s] || !book[d]){puts("Sorry, no line is available."); continue;}mem(vis,0), tpath.clear(), minCnt=minTran=INF;
vis[s]=1;
tpath.push_back(s);
dfs(s,0);
tpath.pop_back();
vis[s]=0;
if(minCnt==INF){puts("Sorry, no line is available."); continue;} // 存在线路与线路之间断开的printf("%d\n",minCnt);
intpreline=0, len=path.size(), preTran;
for(inti=1;i<len;i++)
        {
id=fhash(path[i-1],path[i]);
if(line[id]!=preline)
            {
if(preline!=0) printf("Go by the line of company #%d from %04d to %04d.\n",preline,preTran,path[i-1]);
preline=line[id];
preTran=path[i-1];
            }
        }
printf("Go by the line of company #%d from %04d to %04d.\n",preline,preTran,path[len-1]);
    }
return0;
}