[工学]acm浙大简单题目

《[工学]acm浙大简单题目》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1037GridlandBackgroundForyears,computerscientistshavebeentryingtofindefficientsolutionstodifferentcomputingproblems.Forsomeofthemefficientalgorithmsarealreadyavailable,thesearethe"easy"problemslikesorting,evaluatingapolynomialorfindingtheshortestpathinagraph.Forthe"hard"

2、onesonlyexponential-timealgorithmsareknown.Thetraveling-salesmanproblembelongstothislattergroup.GivenasetofNtownsandroadsbetweenthesetowns,theproblemistocomputetheshortestpathallowingasalesmantovisiteachofthetownsonceandonlyonceandreturntothestartingpoint.ProblemThepresi

3、dentofGridlandhashiredyoutodesignaprogramthatcalculatesthelengthoftheshortesttraveling-salesmantourforthetownsinthecountry.InGridland,thereisonetownateachofthepointsofarectangulargrid.RoadsrunfromeverytowninthedirectionsNorth,Northwest,West,Southwest,South,Southeast,East

4、,andNortheast,providedthatthereisaneighbouringtowninthatdirection.ThedistancebetweenneighbouringtownsindirectionsNorth–SouthorEast–Westis1unit.ThelengthoftheroadsismeasuredbytheEuclideandistance.Forexample,Figure7shows2×3-Gridland,i.e.,arectangulargridofdimensions2by3.In

5、2×3-Gridland,theshortesttourhaslength6.Figure7:Atraveling-salesmantourin2×3-Gridland.InputThefirstlinecontainsthenumberofscenarios.Foreachscenario,thegriddimensionsmandnwillbegivenastwointegernumbersinasingleline,separatedbyasingleblank,satisfying1

6、eoutputforeachscenariobeginswithalinecontaining"Scenario#i:",whereiisthenumberofthescenariostartingat1.Inthenextline,printthelengthoftheshortesttraveling-salesmantourroundedtotwodecimaldigits.Theoutputforeveryscenarioendswithablankline.SampleInput22223SampleOutputScenari

7、o#1:4.00Scenario#2:6.001048IThinkINeedaHouseboatFredMapperisconsideringpurchasingsomelandinLouisianatobuildhishouseon.Intheprocessofinvestigatingtheland,helearnedthatthestateofLouisianaisactuallyshrinkingby50squaremileseachyear,duetoerosioncausedbytheMississippiRiver.Sin

8、ceFredishopingtoliveinthishousetherestofhislife,heneedstoknowifhislandisgoingtobelosttoerosion.Afterdoi