算法设计题
小伙伴们一起去郊游,每人都准备了一份便当。大家对自己的便当都有一个喜爱程度Ai,同时每个便当对其他人有一个吸引力 Bi。小 M 想与小伙伴交换便当,从而得到自己更喜欢的便当。如果小 M 便当的吸引程度大于等于小伙伴对自己便当的喜爱程度时,就可以进行交换,交换所需的沟通时间为 Ti。小 M 便当的吸引力是 1。
为了能尽快享用便当,小 M 想知道获得一个吸引力不小于 D 的便当最少需要多少时间。
哪位大神能给个思路呢?? 算法 设计
[解决办法]
每个人建一个点,点i到点j连一条有向边当且仅当手拿i的便当的时候可以交换到j的便当。边权是Tj。然后就是单源最短路跑一下就完了。