本文主要是介绍浙大PAT 1003题 1003. Emergency，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本题用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;
}
这篇关于浙大PAT 1003题 1003. Emergency的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
