bellmannbsp专题

poj_2240_bellmannbsp;ford

题目描述:    给出货币兑换关系,问是否能用其中一种货币换回更多的值。 解题思路:    bellman-ford。    回顾下:适用于含负权边的图。可检测图中是否存在负权回路。算法简单描述为做n次边松弛操作,用数组D[]记下每个点处的值。若第n次仍然有边可以进行松弛,则说明存在负权回路。否则该D[]求得从源点s到图G的任意丁点v的最短路径D[].   这个题要注意自己和自己兑换的情况。同时