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; }?三个测试点没过
?