#include <stdio.h> #define N 501 #define M 1000000 int rescue[N];// = {1,2,1,5,3} int startP,endP; int path[N]={0}; int size=0; int vex[N][N]={0}; int visit[N]={0}; int maxR=0; int minP=M; int pathcount=1; int pCount=0;//路径指针 void DFS(int start, int end){ int j,i = start; if(start == end){ //找到 int t, sumP=0, sumR=0; for(t=0;t<pCount;t++){ sumP += vex[path[t]][path[t+1]]; sumR += rescue[t]; } sumR += rescue[pCount]; if(sumP == minP) { if(sumR > maxR) { maxR = sumR; } pathcount++; } if(sumP < minP) { minP = sumP; pathcount = 1; maxR = sumR; } return; } else { for(j=0;j<size;j++){ if(vex[i][j] != 0 && visit[j] == 0){ visit[j] = 1; path[++pCount] = j; DFS(j, end); path[pCount--] = 0; visit[j] = 0; } } } } void init(){ int n,pCountt; int i; scanf("%d %d %d %d",&n, &pCountt, &startP, &endP); size = n; for(i=0;i<n;i++){ scanf("%d", &rescue[i]); } int r,c,value; for(i=0;i<pCountt;i++){ scanf("%d %d %d", &r, &c, &value); vex[r][c] = vex[c][r] = value; } visit[startP] = 1; path[0] = startP; DFS(startP, endP); } /* void init(){ int i,n,pCount; startP=0; endP=4; n=5; size = n; // rescue[size] = {1,2,1,5,3}; vex[0][1] = vex[1][0] = 1; vex[0][2] = vex[2][0] = 2; vex[0][3] = vex[3][0] = 1; vex[1][2] = vex[2][1] = 1; vex[2][4] = vex[4][2] = 1; vex[3][4] = vex[4][3] = 2; visit[startP] = 1; path[0] = startP; DFS(startP, endP); } */ int main(){ init(); // printf("%d", vex[399][499]); printf("%d %d", pathcount, maxR); return 0; }
三个测试点没过
相关推荐
代码有详细注释! 1.语言:使用java编程 2.数据结构:使用单链表头插法仿实现栈 3.非递归使用DFS搜索一条路径 4.递归求解所有路径
在Codeblocks中首先用C语言生成一个迷宫并用递归算法求解一条可行的路径
c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘...
自己实现的递归寻路的算法。用到了穷举效率不是很高。 不过递归和回溯算法超经典。以城市地图为例,根据权重,找到最佳路径。文档源码详解。大家可以看看。
递归文件路径+微信红包随机 java的递归算法,寻找电脑某个路径下所有的文件 微信发出200红包,Java递归算法,每个人获得的红包金额随机,拼手气
宏递归宏递归宏递归宏递归宏递归宏递归宏递归宏递归宏递归宏递归
C#递归C#递归C#递归C#递归C#递归C#递归C#递归C#递归C#递归
c#非递归求解迷宫最短路径。源码编写visual studio 2005
该脚本可以扫描指定路径,将符合条件的文件全部找出。你可以添加自己的函数来处理符合条件的文件。如删除某个文件夹里的所有特定文件
Java实现矩阵中的路径(回溯法),采用非递归的回溯法,使用栈模拟递归过程。代码注释详细,可正常运行
函数以递归方式在路径中搜索与通配符表达式(例如“ images *。*”)或正则表达式(例如“ images [0-9]。* \。*”)匹配的文件名。 该函数返回与给定模式匹配的每个文件的完整路径的元胞数组。
大学数据结构课程设计(C++),VisualC++,程序可以正常运行,包括递归和非递归方法寻找迷宫路径。
本段代码主要是使用Java编写的递归获取指定路径下获取匹配后缀文件列表程序,可以做出多种扩展。如有疑问,可以留言,欢迎下载和支持。 本段代码主要是使用Java编写的递归获取指定路径下获取匹配后缀文件列表程序,可以...
利用Prolog实现简单路径判断。 判断给定图的任意结点间路径是否存在。 使用递归方法定义路径。
使用回溯法求解迷宫问题,在这个程序中使用的是递归算法
文件递归-XML递归-树图递归 面试中的常见递归算法:附带截图和详细代码
.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法
简单的递归实现汉诺塔程序,是经典的递归应用程序~
快速选择非递归与递归算法实现
递归和非递归方式计算Ackerman函数。非递归方法用堆栈实现。代码内部有详细的注释说明,比较适于学习。