UVa 10099

The Tourist Guide

from Volume 7. Graph Algorithms and Implementation Techniques

Description

在一个旅游景点。一个旅游团伙，要从一个点到另一个点。但是旅游景点上的每一条路，都有限制车载人数上限。输入旅游景点的图，出发点和目的地，还有游客数。输出最少要多少趟车，才能把所有游客送到目的地。

Solution

从S到T，感觉很像单源最短路径的问题。没错就是单源最短路径问题。只是我们求的不是最短，而且路径上最小值最大。只要改一下Dijkstra的贪心策略即可。