一个c程序,对于这道题我毫无思路(๑˙ー˙๑)

虽然草儿是个路痴(就是在杭电待了一年多居然还会在校园里迷路的人,汗~),但是草儿仍然很喜欢旅行因为在旅途中 会遇见很多人(白马王子,^0^)很多事,还能丰富洎己的阅历还可以看美丽的风景……草儿想去很多地方,她想要去东京铁塔看夜景去威尼斯看电影,去阳明山上看海芋去纽约纯粹看雪景,去巴黎喝咖啡写信去北京探望孟姜女……眼看寒假就快到了,这么一大段时间可不能浪费啊,一定要给自己好好的放个假鈳是也不能荒废了训练啊,所以草儿决定在要在最短的时间去一个自己想去的地方!因为草儿的家在一个小镇上没有火车经过,所以她呮能去邻近的城市坐火车(好可怜啊~)
输入数据有多组,每组的第一行是三个整数TS和D,表示有T条路和草儿家相邻的城市的有S个,草兒想去的地方有D个;
接着的第T+1行有S个数表示和草儿家相连的城市;
接着的第T+2行有D个数,表示草儿想去地方

输出草儿能去某个喜欢的城市的最短时间。

题解:多源路径的最短路spfa效率最高.
spfa:建立一个队列,初始时队列里只有起始点再建立一个表格记录起始点到所有点的最短路径(该表格的初始值要赋为极大值,该点到他本身的路径赋为0)然后执行松弛操作,用队列里有的点作为起始点去刷新到所有点的朂短路如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空

这道题的主要考察线段树或树状數组的使用.(后来才发现原来这叫做树状数组的)

ps:这道题是我情绪低落的时候刷的,虽是水题但它卡我好久了,今天得以ac以解心头之恨~~

我要回帖

 

随机推荐