学步园

本题用Dfs搜索或者Dijkstra算法都可以，当然也有其它的方法。这题感觉是pat中常见的类型，非常重要。

Dfs搜索代码：

#include<stdio.h>
int road[510][510],vst[510],hper[510];
int N,M,C1,C2,shpath=-1,maxhp=-1,cnt=0;
int main(){
  void dfs(int from,int len,int helpers);
  int i,j;
  int c1,c2,l;
  scanf("%d %d %d %d",&N,&M,&C1,&C2);
  for(i=0;i<N;i++){
	scanf("%d",&hper[i]);
	vst[i]=0;
	for(j=0;j<N;j++){
		road[i][j]=-1;
		road[j][i]=-1;
	}
  }

  for(i=0;i<M;i++){
	scanf("%d %d %d",&c1,&c2,&l);
	road[c1][c2]=l;
	road[c2][c1]=l;
  }
  vst[C1]=1;
  dfs(C1,0,hper[C1]);
  printf("%d %d\n",cnt,maxhp);
  return 0;
}
void dfs(int from,int len,int helpers){
  int i,j;
  if(len>shpath&&shpath!=-1){
	return;
  }
  if(from==C2){
	  if(len<shpath||shpath==-1){
		shpath=len;
		maxhp=helpers;
		cnt=1;
	  }
	  else if(len==shpath){
		cnt++;
		if(helpers>maxhp){
			maxhp=helpers;
		}
	  }
	return;
  }
  for(i=0;i<N;i++){
	  if(vst[i]==0&&road[from][i]!=-1){
		vst[i]=1;
		dfs(i,len+road[from][i],helpers+hper[i]);
	    vst[i]=0;
	  }
  }

} 

Dijstra算法代码：

#include<stdio.h>
#define maxint 1<<28
int N,M,C1,C2;
int map[510][510],vst[510],dis[510],hel[510];
int pathcnt[510],pathhel[510];
void init(){
	int i,j;
	for(i=1;i<=N;i++){
		vst[i]=0;
		hel[i]=0;
		dis[i]=maxint;
		pathcnt[i]=0;
		pathhel[i]=0;
		for(j=1;j<=N;j++){
			map[i][j]=map[j][i]=maxint;
		}
	}
}
void Dijstra(){
	int i,j,k;
	dis[C1]=0;
	pathcnt[C1]=1;
	pathhel[C1]=hel[C1]; 
	for(i=1;i<=N;i++){
		int imin=maxint;
		for(j=1;j<=N;j++){
			if(!vst[j]&&dis[j]<imin){
				imin=dis[j];
				k=j;
			}
		}
		vst[k]=1;
		for(j=1;j<=N;j++){
			if(vst[j]==0){ 
				if(dis[j]>dis[k]+map[k][j]){
					dis[j]=dis[k]+map[k][j];
					pathhel[j]=pathhel[k]+hel[j];
					pathcnt[j]=pathcnt[k];
				}
				else if(dis[j]==dis[k]+map[k][j]){
					pathcnt[j]+=pathcnt[k];
					if(pathhel[j]<pathhel[k]+hel[j]){
						pathhel[j]=pathhel[k]+hel[j];	
					}
				}	
			}
			
		}
		if(imin==maxint||k==C2) return;
	}

}
int main(){
	int i,j,from,to,dist;
	scanf("%d %d %d %d",&N,&M,&C1,&C2);
	C1++;
	C2++;
	init();
	for(i=1;i<=N;i++){
		scanf("%d",&hel[i]);	
	}
	for(i=1;i<=M;i++){
		scanf("%d %d %d",&from,&to,&dist);
		map[from+1][to+1]=map[to+1][from+1]=dist;
	}
	Dijstra();
	printf("%d %d\n",pathcnt[C2],pathhel[C2]);
	return 0;
}