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