PAT 1003 Emergency 递归记录访问路径

?

?

#include <stdio.h>  #define N 501#define M 1000000int 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;  }

?三个测试点没过

?