资源描述：
《面试题 - 副本》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、Problemone:TrainsThelocalcommuterrailroadservicesanumberoftownsinKiwiland.Becauseofmonetaryconcerns,allofthetracksare'one-way.'Thatis,aroutefromKaitaiatoInvercargilldoesnotimplytheexistenceofaroutefromInvercargilltoKaitaia.Infact,evenifbothoftheseroutesdohappentoexist,theyaredistinctandarenotnec
2、essarilythesamedistance!Thepurposeofthisproblemistohelptherailroadprovideitscustomerswithinformationabouttheroutes.Inparticular,youwillcomputethedistancealongacertainroute,thenumberofdifferentroutesbetweentwotowns,andtheshortestroutebetweentwotowns.Input:Adirectedgraphwhereanoderepresentsatownan
3、danedgerepresentsaroutebetweentwotowns.Theweightingoftheedgerepresentsthedistancebetweenthetwotowns.Agivenroutewillneverappearmorethanonce,andforagivenroute,thestartingandendingtownwillnotbethesametown.Output:Fortestinput1through5,ifnosuchrouteexists,output'NOSUCHROUTE'.Otherwise,followtheroutea
4、sgiven;donotmakeanyextrastops!Forexample,thefirstproblemmeanstostartatcityA,thentraveldirectlytocityB(adistanceof5),thendirectlytocityC(adistanceof4).1.ThedistanceoftherouteA-B-C.2.ThedistanceoftherouteA-D.3.ThedistanceoftherouteA-D-C.4.ThedistanceoftherouteA-E-B-C-D.5.ThedistanceoftherouteA-E-D
5、.//算法1，用于查表计算6.ThenumberoftripsstartingatCandendingatCwithamaximumof3stops.Inthesampledatabelow,therearetwosuchtrips:C-D-C(2stops).andC-E-B-C(3stops).7.ThenumberoftripsstartingatAandendingatCwithexactly4stops.Inthesampledatabelow,therearethreesuchtrips:AtoC(viaB,C,D);AtoC(viaD,C,D);andAtoC(viaD,
6、E,B).//算法2，只计算边的条数，使用dfs解决8.Thelengthoftheshortestroute(intermsofdistancetotravel)fromAtoC.//使用经典的最短路径解决9.Thelengthoftheshortestroute(intermsofdistancetotravel)fromBtoB.10.numberofdifferentroutesfromCtoCwithadistanceoflessthan30.Inthesampledata,thetripsare:CDC,CEBC,CEBCDC,CDCEBC,CDEBC,CEBCEBC,CE
7、BCEBCEBC.//某个范围内的路径数，。使用dfs解决TestInput:Forthetestinput,thetownsarenamedusingthefirstfewlettersofthealphabetfromAtoD.Aroutebetweentwotowns(AtoB)withadistanceof5isrepresentedasAB5.Graph:AB5,BC4,CD8,DC8,DE6,AD5,CE2,EB3,AE7Expec
