某公司于乙城市的销售点急需一批成品，该公司成品生产基地在甲城市。 甲城市与乙城市之间共有n 座城市，互相以公路连通。甲城市、乙城市以及其它各城市之间的公路连通情况及每段公路的长度由矩阵 M1 给出。 每段公路均由地方政府收取不同额度的养路费等费用，具体数额由矩阵M2 给出。 请给出在需付养路费总额不超过1500 的情况下，该公司货车运送其产品从甲城市到乙城市的最短运送路线。 具体数据参见文件： M1.txt: 各城市之间的公路连通情况及每段公路的长度矩阵(有向图) 甲城市

Flatopia是个很平的地方，政府想要修高速公路，以解决交通问题。高速公路系统能使得驾驶能够不出离此系统就能够在任意两城之间通行。城镇编号1~N，每条高速路连接两个城镇，所有高速路都是直线的，双向使用的。但是一个驾驶员只能在公路的尽头的城镇改变线路。当地政府想要尽量减少所需修建最长公路的长度，然而，必须保证每一个城镇都是可以达到的。 输入： 处理情况。 由一个矩阵代表了每两个镇之间的距离，每个情况末尾是空行。 二、 算法分析： 题目抽象后可得，给定一个图，要求找到一个