Dayi Lin, Ph.D.

Staff Researcher, AI & Software Engineering

Tag: 单源最短路

POJ-1062 解题报告

题意简述 你想娶酋长的女儿,但酋长要求你给一定数额金钱的聘礼。除了金钱外,酋长也允许你用部落里其他人的某物品加上一点钱作为聘礼。而其他人的物品也可以通过指定的另外一些人的某物品加上一些金钱获得。部落里的每个人有一个等级。你的整个交易过程涉及的人的等级只能在一个限定的差值内。问你最少需要多少金钱才能娶到酋长女儿。假定每个人只有一个物品。 例: 最高最低等级差不超过1,共4个物品 酋长的女儿    等级3     要求现金10000元     或甲的物品+8000元     或乙的物品+5000元 甲的物品     等级2     要求现金1000元      或丙的物品+200元 乙的物品        等级2     要求现金3000元      或丙的物品+200元 丙的物品        等级2     要求现金50元 在这个例子中,最少花费方案是:买丙的东西(50)换乙的东西(+200)换酋长女儿(+5000)一共5250元。