1072. Gas Station (30)

#include<cstdio>#include<iostream>#include<string>#include<algorithm>#include<map>#include<sstream>using namespace std;const int INF=1000000;int MinDist[12][1020];int ma[1020][1020];int N,M,R,MaxDist,SumTemp;int isread[1020];int dijkstra(int node){//常规就行了，加一点细节的判断 	SumTemp=0;	int i,min=INF,MinRe=INF;	for(i=0;i<1020;i++){		isread[i]=0;		MinDist[node-N][i]=INF;	}	int start=node;	MinDist[node-N][start]=0;	while(1){		min=INF;		for(i=N+M;i>=1;i--){			if(MinDist[node-N][i]<min&&isread[i]==0){				min=MinDist[node-N][i];				start=i;			}		}		if(isread[start]==1)			break;		isread[start]=1;		if(start<=N){			SumTemp+=MinDist[node-N][start];		if(MinDist[node-N][start]<MinRe)			MinRe=MinDist[node-N][start];		if(MinDist[node-N][start]>MaxDist)			return -2;		}		for(i=1;i<N+M+1;i++){			if(MinDist[node-N][i]>MinDist[node-N][start]+ma[i][start]&&isread[i]==0){				MinDist[node-N][i]=MinDist[node-N][start]+ma[start][i];			}		}	}	return MinRe;}int exchange(string s){//返回string转化成int量的结果 	int answer;	if(s[0]=='G'){		stringstream tt(s.substr(1,s.size()));		tt>>answer;		return answer+N;	}	else{		stringstream tt(s);		tt>>answer;		return answer;	}}int main(){	int i,j,c,Mini,suf=INF;	double sum=0,min=-1;	string a,b;	cin>>N>>M>>R>>MaxDist;	for(i=0;i<1020;i++)		for(j=0;j<1020;j++)			ma[i][j]=INF;	for(i=0;i<R;i++){		cin>>a>>b>>c;		ma[exchange(a)][exchange(b)]=c;//建立无向图 		ma[exchange(b)][exchange(a)]=c;	}	for(i=N+1;i<N+M+1;i++){		j=dijkstra(i);//对于各个可能建加油站的点用单源最短路劲算法，ps可能拼错了 		if(j>min||(j==min&&suf>SumTemp)){			min=j;			Mini=i;			suf=SumTemp;		}	}	if(min==-1){		PRintf("No Solution/n");		return 0;	}	cout<<"G"<<Mini-N<<endl;	for(i=1;i<=N;i++)		sum+=MinDist[Mini-N][i];	printf("%.1f %.1f/n",min,sum/N);}