ACM

2016HUAS_ACM暑假集训3-C - Til the Cows Come Home

2016HUAS_ACM暑假集训3-C - Til the Cows Come Home
        题目意思大概是给出T条边,N个点。求第一个点到第N个点的最短距离。开始是n*n次直接循环,然后挂了,总是出现莫名其妙的数字(memset造成,memset使用要谨慎啊!!!)。后来看博客发现用Dijkstra算法求。从1开始,找出距离当前位置距离最小而且最远的点,然后通过这个点找他能到达的边的距离和当前... 继续阅读 »
ACM

2016HUAS_ACM暑假集训3-G - 还是畅通工程

2016HUAS_ACM暑假集训3-G - 还是畅通工程
G - 还是畅通工程        题目意思是找使公路路径最小。也就是最小生成树。但是这里应该有多种解法,我看了两种解法,一种是Prim最小生成树算法,一种是使用类似并查集思想的Kruskal算法。个人感觉Kruskal算法比prim算法好理解一些,但是Kruskal算法的效率要比Prim低。题目:飞机票直达... 继续阅读 »