本题是典型的图论题,关键在于建立模型。
  首先,构造图G=(V,E),其中Vi代表第I个城市,如果城市I与城市J之间有航班,则在点I、J间连一条边,边的权值即为从I到J所需费用。在这个图的基础上,我们可以看到,当M=0(既不需考虑优惠情况时),显然一次dijkstra算法就能解决问题--当然,这不是我们题目所求,但我们是否可以由此受启发:能否根据题意改造图,并利用其顺利的解决问题?

  我们再看一看题目:"每张优惠券可以作用于一条航线,使全队通过此航线的费用减半;多张优惠券用于同一条线路,其效果叠加--即在一条航线上用两张优惠券,其费用降为原费用的1/4,依此类推。"也就是说,从城市I到城市J(当它们之间有航线时),设其费用为W,则所花的费用有M+1种可能:不用优惠券,费用为W;用一张优惠券,为W/2;……用M张优惠券,费用为W/(2m)。--说得更直接些,就是在我们原先构造的图G中,互相连通的两个点,实际上有M+1种不同的权值!理所当然,很多人一定会想到一种常用的方法--拆点,在原先图的基础上建立新图。

  下面我们详细阐述一下建立新图的过程:为了完整地表示出优惠券的使用对费用的影响,我们将原图中的Vi拆成M+1个点,分别标记为Vi,0,Vi,1……Vi,m。在Vi,j中,j表示已使用了j张优惠券。而对于每两组可以连通的点(这里暂且设为点A、B),我们都要对其添加有向边。有向边的构造按以下步骤进行:

  1.图的起点是V1,0,终点是Vn,m。
  2.仅当Va,i与Vb,j可以连通时,我们才有可能在它们之间连边。
  3.在1的基础上,仅当I<=J时,我们才从Va,i连一条边到Vb,j;同理,仅当J<=I时,我们才从Vb,j连一条边到Va,I。这就保证了从起点到终点一定使用了M张优惠券。
  4.如果从Va,i可以连边到Vb,j,那么这条边的权值为[Wa,b/2(j-i)](Wa,b指在原图中点A、B间的权值)。
  下面我们举个例子:
  设M=2,有两个点A、B,它们之间不用优惠券时权值为8,如图1所示。

  对这个图进行拆点、加边处理之后,我们得到的新图如图2所示:
  (为了表示上的方便,图中只表示出由A到B的边)
  这样一来,我们只需套用dijkstra算法,求出V1,0至Vn,m的最短路,即为题目所求。

  注:本题的数据量为(N<=80,M<=20),拆成的点可达80*21=1680个,如果把点与点的关系直接存贮下来显然是不行的。其实,我们只需记录下每个点是否被到达,当前获得的最小费用以及前一个点的标号,而边的权值可以在求最短路的同时计算得到。

[img]http://www.chinaschool.org/aosai/lwjl/images/02-0316.gif[/img]