本题是典型的图论题，关键在于建立模型。
　　首先，构造图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个，如果把点与点的关系直接存贮下来显然是不行的。其实，我们只需记录下每个点是否被到达，当前获得的最小费用以及前一个点的标号，而边的权值可以在求最短路的同时计算得到。