面朝大海,春暖花开
从现在起,做一个幸福的人。 读书、工作、周游世界。 想有一所房子,面朝大海,春暖花开
May 22, 2013
Codility - Iota 2011 - shortest_adj_seq
题目见
https://codility.com/demo/take-sample-test/iota2011/
思路比较明显:根据给出数据,构造无向图,求出起点到终点的最短路径即可。
显然Dijkstra算法,每条边的长度为1,可以根据此优化,一层一层往后遍历,这样就不需要单独记录每个点与起点的距离,只需记录当前是第几层,否则的话在最大的数据集上会超时(可能是跟我用了好几个map和set有关,不过有轮子可用就不想自己造了…… )
代码见
https://github.com/phiphy/codility/blob/master/shortest_adj_seq-iota_2011.cpp
No comments:
Post a Comment
Older Post
Home
View mobile version
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment