用分支定界算法求以下问题：
某公司于乙城市的销售点急需一批成品，该公司成品生产基地在甲城市。甲城市与乙城市之间共有 n 座城市，互相以公路连通。甲城市、乙城市以及其它各城市之间的公路连通情况及每段公路的长度由矩阵M1 给出。每段公路均由地方政府收取不同额度的养路费等费用，具体数额由矩阵M2 给出。
请给出在需付养路费总额不超过 1500 的情况下，该公司货车运送其产品从甲城市到乙城市的最短运送路线。
具体数据参见文件：
m1.txt: 各城市之间的公路连通情况及每段公路的长度矩阵(有向图); 甲城市为城市Num.1，乙城市为城市Num.50。 m2.txt: 每段公路收取的费用矩阵（非对称）。
思想：利用Floyd算法的基本方法求解。
程序实现流程说明：
1.将m1.txt和m2.txt的数据读入两个50×50的数组。
2.用Floyd算法求出所有点对之间的最短路径长度和最小费用。 3.建立一个堆栈，初始化该堆栈。
4.取出栈顶的结点，检查它的相邻的所有结点，确定下一个当前最优路径上的结点，被扩展的结点依次加入堆栈中。在检查的过程中，如果发现超出最短路径长度或者最小费用，则进行”剪枝”，然后回溯。 5.找到一个解后，保存改解，然后重复步骤4。
6.重复步骤4、5，直到堆栈为空，当前保存的解即为最优解。
时间复杂度分析：
Floyd算法的时间复杂度为O(N)，N为所有城市的个数。
3该算法的时间复杂度等于DFS的时间复杂度，即O(N+E)。其中，E为所有城市构成的有向连通图的边的总数。但是因为采用了剪枝，会使实际运行情况的比较次数远小于E。
求解结果： 算法所得结果:
甲乙之间最短路线长度是:464 最短路线收取的费用是:1448 最短路径是:
1 3 8 11 15 21 23 26 32 37 39 45 47 50
C源代码（注意把m1.txt与m2.txt放到与源代码相同的目录下， 下面代码可直接复制运行）：
#include
#define N 50 #define MAX 52
void input(int a[N][N],int b[N][N]);
void Floyd(int d[N][N]);
void fenzhi(int m1[N][N],int m2[N][N],int mindist[N][N],int mincost[N][N]); int visited[N],bestPath[N];
void main() { clock_t start,finish; double duration;
int i,j,mindist[N][N],mincost[N][N],m1[N][N],m2[N][N]; /* m1[N][N]和m2[N][N]分别代表题目所给的距离矩阵和代价矩阵 */
// int visited[N],bestPath[N]; FILE *fp,*fw; // system(\ time_t ttime; time(&ttime); printf(\ start=clock(); for(i=0;i { } mindist[i][i]=9999; mincost[i][i]=0; Floyd(mindist); /* 用弗洛伊德算法求任意两城市之间的最短距离，结果存储在数组mindist[N][N]中 */ /* fw=fopen(\ for(i=0;i finish=clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf( \ //*/ } void Floyd(int d[N][N]) /* 弗洛伊德算法的实现函数 */ { int v,w,u,i; for(u=0;u } //printf(\ d[v][w]=d[v][u]+d[u][w]; } } } void input(int a[N][N],int b[N][N]) /* 把矩阵b赋值给矩阵a */ { int i,j; for(i=0;i void fenzhi(int m1[N][N],int m2[N][N],int mindist[N][N],int mincost[N][N]) { int stack[MAX],depth=0,next,i,j; /* 定义栈，depth表示栈顶指针；next指向每次遍历时当前所处城市的上一个已经遍历的城市 */ int bestLength,shortestDist,minimumCost,distBound=9999,costBound=9999; int cur,currentDist=0,currentCost=0; /* cur指向当前所处城市，currentDist和currentCost分别表示从甲城市到当前所处城市的最短距离和最小代价， currentDist和currentCost初值为0表示从甲城市出发开始深度优先搜索 */ stack[depth]=0; /* 对栈进行初始化 */ stack[depth+1]=0; visited[0]=1; /* visited[0]=1用来标识从甲城市开始出发进行遍历，甲城市已被访问 */ while(depth>=0) /* 表示遍历开始和结束条件，开始时从甲城市出发，栈空，depth=0；结束时遍历完毕，所有节点均被出栈，故栈也为空，depth=0 */ /* 整个while（）循环体用来实现从当前的城市中寻找一个邻近的城市 */ { cur=stack[depth]; /* 取栈顶节点赋值给cur，表示当前访问到第cur号城市 */ next=stack[depth+1]; /* next指向当前所处城市的上一个已经遍历的城市 */ for(i=next+1;i */ } depth--; currentDist-=m1[stack[depth]][stack[depth+1]]; currentCost-=m2[stack[depth]][stack[depth+1]]; visited[stack[depth+1]]=0; else /* i!=N,表示for循环的终止是由于寻找到了当前城市的一个可行的邻近城市 */ { // printf(\ currentDist+=m1[stack[depth]][i]; /* 把从当前所处城市到所找到的可行城市的距离加入currentDist currentCost+=m2[stack[depth]][i]; /* 把从当前所处城市到所找到的可行城市的代价加入currentCost */ depth++; /* 所找到的可行城市进栈 */ stack[depth]=i; /* 更新栈顶指针，指向所找到的可行城市 */ stack[depth+1]=0; visited[i]=1; /* 修改所找到的城市的访问标志 */ if(i==N-1) /* i==N-1表示访问到了乙城市，完成了所有城市的一次搜索，找到一条通路 */ { // printf(\ for(j=0;j<=depth;j++) /* 保存当前找到的通路所经过的所有节点 */ bestPath[j]=stack[j]; bestLength=depth; /* 保存当前找到的通路所经过的所有节点的节点数 */ shortestDist=currentDist; /* 保存当前找到的通路的距离之和 */ minimumCost=currentCost; /* 保存当前找到的通路的代价之和 */ //costBound=currentCost; distBound=currentDist; /* 更新剪枝的路径边界，如果以后所找到的通路路径之和大于目前通路的路径之和，就剪枝 */ if(minimumCost>1500) continue; /* 如果当前找到的通路的代价之和大于1500，则放弃这条通路 */ printf(\最短路径:=,路径代价:=,所经历的节点数目:=,所经历的节点如下:\\n\输出找到的通路的结果 */ bestPath[bestLength]=49; for(i=0;i<=bestLength;i++) /* 输出所找到的通路所经过的具体的节点 */ printf(\ printf(\ 的通路 */ } depth--; /* 连续弹出栈顶的两个值，进行回溯，开始寻找新的可行currentDist-=m1[stack[depth]][stack[depth+1]]; currentCost-=m2[stack[depth]][stack[depth+1]]; visited[stack[depth+1]]=0; depth--; currentDist-=m1[stack[depth]][stack[depth+1]]; currentCost-=m2[stack[depth]][stack[depth+1]]; visited[stack[depth+1]]=0; // getchar(); } } }