最短路 http://acm.hdu.edu.cn/showproblem.php?pid=2544
    赤裸裸的最短路

A Walk Through the Forest http:
//acm.hdu.edu.cn/showproblem.php?pid=1142
"He considers taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A." 重在理解这句话。先求出所有顶点到顶点2的最短路(以顶点2为源点做一次Dijkstra),然后从顶点1开始记忆化搜索。
If (d[u] 
> d[v])
Sum 
+= bfs(v);
    
Minimum Transport Cost  http:
//acm.hdu.edu.cn/showproblem.php?pid=1385
    Floyd路径输出,题目要按路径的字典序输出;
    
if (p[i][k] + p[k][j] == map[i][j] && path[i][k] < path[i][j])
            path[i][j] 
= path[i][k];
    即可
    
Arbitrage http:
//acm.hdu.edu.cn/showproblem.php?pid=1217
    问题是是否可以盈利,如果我们把汇率看成边,当一个点通过某些路径返回到自己后的值大于1,则盈利;

A strange lift http:
//acm.hdu.edu.cn/showproblem.php?pid=1548
    因为边的权值都为1,BFS,Dijkstra都可以

 

一个人的旅行http://acm.hdu.edu.cn/showproblem.php?pid=2066

    需要构图,另外建立2个点,分别各乘车城市,草儿想去的地方相连,权值为0;则问题转化为单源最短路问题;



The shortest path http:
//acm.hdu.edu.cn/showproblem.php?pid=2224
    Bitonic path (详见《算法导论》 P217)
    一个人从p1严格地增的走到pn,然后再严格递减的回到p1;求总路径的最小值;
    网上看到很多解题报告看的我直冒汗    
    对于1 
<= i <= j <= n, 我们定义P(i, j)是一条包含了P1, P2, P3 …… Pj的途径; 这条路径可以分成2部分:递减序列与递增序列,起点是Pi(1 <= i <= j),拐点是P1,终点是Pj, P[i, j]为其最小值;那么状态转移方程为:
    b[
1,2= |P1P2|,
    i 
< j-1时, b[i,j] = b[i,j-1+ |Pj-1Pj|    点Pj-1在递增序列中,
    i 
= j-1时, b[i,j] = min{ b[k,j-1+ |PkPj|1<= k < j-1 }  点Pj-1在递减序列中
    b[n,n] 
= b[n-1,n] + |Pn-1Pn|
    
The Shortest Path http:
//acm.hdu.edu.cn/showproblem.php?pid=2807
    Floyd与多次Dijkstra都可以;
A
*B=C, A,C连同;
我们不妨可以对于每两个城市相乘,把得到的矩阵跟非A,B比较,而不要对于A,C去寻找是否存在这样一个B,结果很容易超时
    另外,这里有个优化是矩阵的比较 (2维转化成1维)
posted on 2009-12-04 17:12 西风萧瑟 阅读(2592) 评论(1)  编辑 收藏 引用 所属分类: 图论

评论:
# re: HDU 最短路题目小结 2009-12-05 12:01 | Geek.tan
总结的不错,希望LZ多总结一些专题,方便练习  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理