本文主要是介绍浙大PAT 1072题 1072. Gas Station，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*
本题的题意开始没有理解，以为最优的第一条件就是平均值最小，但不是这样的。
第一条件：所有候选点中到house最小值最大的那个候选点，第一个测试用例中G1的最小值为2，
G2的最小值为1，G3的最小值为2，所以选取候选点G1和G3继续比较；
4 2 4 3
3 1 3 4
5 3 2 4
G1
2.0 3.3
第二条件：平均值最小，第一个测试用例中，G1的平均值小于G3，所以最优解为G3；
第三条件：序号最小；
*/
#include<stdio.h>
#include<string.h>
#define Inf 1<<30
int n,m,k,d;
int map[1100][1100],vst[1100],dis[1100];
typedef struct{int total;int imin;int mark;
}Node;
Node node[20];
void Dijstra(int index){int i,j,k,imax;dis[index]=0;for(i=1;i<n+m;i++){imax=Inf;for(j=1;j<=1000+m;j++){if(!vst[j]&&dis[j]<imax){imax=dis[j];k=j;}if(j==n) j=1000;}vst[k]=1;for(j=1;j<=1000+m;j++){if(!vst[j]){if(dis[k]+map[k][j]<dis[j]){dis[j]=dis[k]+map[k][j];}}if(j==n) j=1000;}}}
int main(){int i,j,dist;char from[10],to[10];int fsum,tsum,tmp;scanf("%d %d %d %d",&n,&m,&k,&d);for(i=1;i<=1010;i++){for(j=1;j<=1010;j++){map[i][j]=Inf;}}for(i=0;i<k;i++){scanf("%s %s %d",from,to,&dist);int lenf=strlen(from);tmp=1;if(from[0]=='G'){fsum=1000+from[lenf-1]-'0';for(j=lenf-2;j>=1;j--){tmp=tmp*10;fsum=fsum+(from[j]-'0')*tmp;}}else{fsum=from[lenf-1]-'0';for(j=lenf-2;j>=0;j--){tmp=tmp*10;fsum=fsum+(from[j]-'0')*tmp;}}int lent=strlen(to);tmp=1;if(to[0]=='G'){tsum=1000+to[lent-1]-'0';for(j=lent-2;j>=1;j--){tmp=tmp*10;tsum=tsum+(to[j]-'0')*tmp;}}else{tsum=to[lent-1]-'0';for(j=lent-2;j>=0;j--){tmp=tmp*10;tsum=tsum+(to[j]-'0')*tmp;}}//printf("%d %d\n",fsum,tsum);map[fsum][tsum]=map[tsum][fsum]=dist;}int rtotal,rmin,flag;for(i=1001;i<=1000+m;i++){for(j=1;j<=1010;j++){vst[j]=0;dis[j]=Inf;}Dijstra(i);//for(j=1;j<=n;j++)//printf("%d ",dis[j]);//printf("\n");flag=0;rtotal=0;for(j=1;j<=n;j++){if(dis[j]<=d){rtotal=rtotal+dis[j];}else{flag=1;}}if(flag){node[i-1000].mark=0;}else{node[i-1000].mark=1;node[i-1000].total=rtotal;rmin=Inf;for(j=1;j<=n;j++){if(dis[j]<rmin)rmin=dis[j];}node[i-1000].imin=rmin;}}int rindex=-1,maxmin=-1,maxtotal=Inf;for(i=1;i<=m;i++){if(node[i].mark){if(node[i].imin>maxmin){maxmin=node[i].imin;maxtotal=node[i].total;rindex=i;}else if(node[i].imin==maxmin){if(node[i].total<maxtotal){maxtotal=node[i].total;rindex=i;}}}}if(rindex==-1){printf("No Solution\n");}else{printf("G%d\n",rindex);printf("%.1f %.1f\n",node[rindex].imin*1.0,node[rindex].total*1.0/n);}return 0;
}
这篇关于浙大PAT 1072题 1072. Gas Station的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
