求出最短距离的方案。
这次也是搭配着矩形图来解决
在这里0就是代表自己相同点重合，无穷则代表两点之间没有关系，里面大于0的数字是两点之间的距离
举例子：
输入1 2 2 意思就是顶点1指向顶点2 两点之间距离为2
输入4 5 5 意思就是顶点4指向顶点5 两点之间距离为5
将顶点之间指向方向以及，两点之间距离等信息放在表中，在利用表中数据来求出
输入内容：
5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3
第一行 第一个5 的意思是创建5*5的表格 第二个8是等下输入8行 后面8行 就是8组(两个顶点+距离) 每组第一个指向第二个
代码：
#include <stdio.h> int min=99999999,book[101],n,e[101][101]; //cur是当前所在的城市编号，dis是当前已经走过的路程 void dfs(int cur,int dis) { int j; //如果当前走过的路已经大于之前找到的最短路了，就可以返回了 if(dis>min) return; if(cur==n) //判断是否达到目标 { if(dis<min) min = dis; return; } //依次1-n个城市尝试 for(j=1;j<=n;j++){ if(e[cur][j]!=99999999&&book[j]==0) { book[j]=1; //标记已经访问了 dfs(j,dis+e[cur][j]); //从该城市出发继续寻找目标 book[j]=0; //访问完要取消访问 } } return; } int main() { int i,j,m,a,b,c; scanf("%d%d",&n,&m); //初始化二维矩阵 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) e[i][j]=0; else e[i][j]=99999999; for(i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); e[a][b] = c; } //进行标记 book[1]=1 book[1]=1; dfs(1,0); //从第一个点开始出发，0表示走过的路径 printf("%d",min); return 0; }
最后运行结果为：9
整体大概过程
这里的9999999假设为无穷，e数组是个二维数组 就是表格用来存放关于顶点之间信息
book数组用来保存是否访问过该节点
第一步：输入表格的长度以及下面几组顶点方向及距离，给表格首先赋全值，后面根据8行再次填充对应表格位置的长度。
第二步：book的首位地址为1表示已经访问过了，进入dfs
先看其中for循环，首先第一步访问第一行数据，根据判断条件到第二个点满足，于是先给book数组对应记上已经访问过
紧接着进行调用自身进入第二组循环，(此时第一组for循环并没有执行完)，在第二组循环中找到满足条件为3，book数组记上
现在进行第三行 (此时一，二组都没执行完) 第三行中第一个已经访问过，后面有找到对应的位置4 ， book数组记上
进入第四行了 (此时一，二，三组都没执行完) 第四行中找到对应点为5 book数组记上
进入第五行 也就是目的点了
找到终点了，应当给出条件让它结束了 此时求出第一组例子的暂且最小值
此时是不是就结束了，并没有之前一二三组循环并没有结束 ，
我们回到第四行继续执行
5这个点找完后 这个循环也结束了
那么回到 第三个循环 这里最主要的一点就是在这个时候如果又找到下一个点
那么之前book中存的不还是生效嘛 所以在每次调用自身之后要将book数组中对应位置清0这步骤很关键
这样到下一个访问方案时才能够继续 按照之前的步骤 只要第一行遍历结束后整个过程就结束了，此时也会得到最小距离min
————————————————
