PAT 1003 Emergency

 

#include <stdio.h>  

#define N 501

int rescue[N] = {1,2,1,5,3};
int startP,endP;
int res[N] = {0};
int dist[N];//距离值   
int path[N]={0};  
int size=0;
int vex[N][N]={0};  
int visit[N]={0};
int max[N]={0};  

void DFS(int start, int end){   
    int j,i = start;
	
	if(start == end){
		//找到或没找到
		return;
	} else {
		for(j=0;j<size;j++){
			if(vex[i][j] != 0 && visit[j] == 0){
				visit[j] = 1;
//				path[j] = path[i];
				if(dist[j] == dist[i] + vex[i][j]){
					path[j]++;
					res[j] = res[i] + rescue[j];
					if(res[j] > max[j]) {
						max[j] = res[j];
					} else{
						res[j] = max[j];
					}
				}
				if(dist[j] > dist[i] + vex[i][j]){
					dist[j] = dist[i] + vex[i][j];
					path[j] = 1;
					res[j] = res[i] + rescue[j];
					max[j] = res[j];
				}
				DFS(j, end);

				visit[j] = 0;
				//res[end] +=rescue[i];
			}
		}
	}
}  
/*
void init(){ 
    int n,pCount; 
    int i; 
    scanf("%d %d %d %d",&n, &pCount, &startP, &endP); 
    size = n; 
     
    for(i=0;i<n;i++){ 
        scanf("%d", &rescue[i]); 
    } 
 
    int r,c,value; 
     
    for(i=0;i<pCount;i++){ 
        scanf("%d %d %d", &r, &c, &value); 
        vex[r][c] = vex[c][r] = value; 
    }

  	for(i=0;i<N;i++){
		dist[i] = 1000000;
	}
	
	visit[startP] = 1;  
    dist[startP] = 0;  
	path[startP] = 1;
	max[startP] = res[startP] = rescue[startP];

    DFS(startP, endP); 
} 
*/

void init(){  
    int i,n,pCount;
	startP=0;
	endP=4;
    n=5;  
    size = n;  
    pCount=7;  
//  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;  
	
	for(i=0;i<N;i++){
		dist[i] = 1000000;
	}

	visit[startP] = 1;  
    dist[startP] = 0;  
	path[startP] = 1;
	max[startP] = res[startP] = rescue[startP];

    DFS(startP, endP);  
}  

int main(){  
    init();  
	
//  printf("%d", vex[399][499]);  
	printf("%d %d", path[endP], max[endP]);
    return 0;  
}

 两个测试点没过

 

#include <stdio.h>  

#define N 501  
  
int rescue[N];  
int res[N]={0};  
int dist[N]={0};//距离值   
int pred[N]={-1};//前驱   
int path[N]={0};  
int size=0;  
int queue[N+1]={-1};  
int vex[N][N]={0};  
int visit[N]={0};  

void updateRes(int pre){
//	printf("hello1---[%d]\n", pre);
	int i;
	if(pre != -1){
		for(i=0;i<size;i++){
			if(pred[i] == pre && i != pre){
				printf("hello");
				res[i] = res[pre] + rescue[i];
				updateRes(i);
			}
		}
		if(i == size) updateRes(-1);
	} else {
		return;
	}
}

void BFS(int start, int end){  
    //队列头尾指针  
    int front=0,rear=0;  
    queue[++rear]=start;  
    visit[start] = 1;
    dist[start] = 0;
	path[start] = 1;
	res[start] = rescue[start];
    int i,j;  
    while(front!=rear){  
        i = queue[++front];  
        for(j=0;j<size;j++){  
            if(vex[i][j] != 0){  
                if(visit[j] == 0){  
                    queue[++rear] = j;  
                    dist[j] = dist[i] + vex[i][j];  
                    path[j] = path[i];
                    res[j] = res[i] + rescue[j];
                    visit[j] = 1;  
                    pred[j] = i;  
                }else { 
					
                    if(j!=start && j != pred[j]){  
						if(dist[j] == dist[i] + vex[i][j]){
							if(res[j] < res[i] + rescue[j]){
								res[j] = res[i] + rescue[j];
								pred[j] = i;
								updateRes(j);
							}
                            path[j]++;
                        }
                        if(dist[j] > dist[i] + vex[i][j]) {  
                            dist[j] = dist[i] + vex[i][j];  
                            res[j] = res[i] + rescue[j];  
                            pred[j] = i;  
                            path[j] = 1;  
							updateRes(j);
                        }    
                    }  
					
                }  
            }  
        }  
    }  
}  
 
void init(){ 
    int n,pCount,startP,endP; 
    int i; 
    scanf("%d %d %d %d",&n, &pCount, &startP, &endP); 
    size = n; 
     
    for(i=0;i<n;i++){ 
        scanf("%d", &rescue[i]); 
    } 
 
    int r,c,value; 
     
    for(i=0;i<pCount;i++){ 
        scanf("%d %d %d", &r, &c, &value); 
        vex[r][c] = vex[c][r] = value; 
    } 
    BFS(startP, endP); 
	printf("%d %d", path[endP], res[endP]);  
} 
  

void init(){  
    int n,pCount,startP=0,endP=5;  
    int i;  
    n=6;  
    size = n;  
    pCount=6;  
//  rescue[size] = {1,2,1,5,3};  
    int r,c,value;  
    vex[0][1] = vex[1][0] = 1;  
    vex[0][2] = vex[2][0] = 3;  
    vex[2][3] = vex[3][2] = 1;  
    vex[1][2] = vex[2][1] = 1;  
    vex[2][4] = vex[4][2] = 1;  
    vex[4][5] = vex[5][4] = 1;  
  
    BFS(startP, endP);  
	printf("%d %d", path[endP], res[endP]);  
}  
 
int main(){  
    init();  
    return 0;  
}

 四个测试点没过