May 22, 2013

Codility - Iota 2011 - shortest_adj_seq

题目见 https://codility.com/demo/take-sample-test/iota2011/

思路比较明显:根据给出数据,构造无向图,求出起点到终点的最短路径即可。

显然Dijkstra算法,每条边的长度为1,可以根据此优化,一层一层往后遍历,这样就不需要单独记录每个点与起点的距离,只需记录当前是第几层,否则的话在最大的数据集上会超时(可能是跟我用了好几个map和set有关,不过有轮子可用就不想自己造了…… )

No comments:

Post a Comment