PAT 1072 가스 스테이션 - Dijkstra 알고리즘

원제 링크
1072 Gas Station
사고의 방향
제목 의 대 의 는 n 개의 주민 점 과 m 개의 주유소 가 존재 한다.지금 은 이 m 개 주유소 중 하 나 를 골 라 서 이 주유소 에서 모든 주민 점 에서 가장 짧 은 거리의 최 단 거 리 를 최대 로 하고 입력 에서 지정 한 범 위 를 초과 해 서 는 안 된다 고 요구 해 야 한다.주의해 야 할 것 은 최 단 거 리 를 계산 할 때 는 주유소 와 주민 점 사이 에 도 접근 할 수 있 는 경로 가 있 기 때문에 주민 점 과 주유 소 를 고려 해 야 한 다 는 점 이다.편 의 를 위해 주유소 번 호 를 n + 1 ~ n + m 사이 로 바 꿉 니 다.나 는 이 단계 가 너 에 게 매우 간단명료 할 것 이 라 고 생각한다.
코드

#include 
using namespace std;
int n,m,k,range; 
const int inf = 0x3f3f3f;
int graph[1020][1020];//        
int dis[1020],ans[1020];//            
int ansid = -1;
double ansmin = -1,ansave = inf;
void dijkstra(int s){
     
	//        s      。             ？？
	fill(dis,dis+1020,inf);
	bool visited[1020];
	fill(visited,visited+1020,false);
	dis[s] = 0; 
	bool isok = true;
	double tmpmin = inf;
	double tmpsum = 0;//            
//	cout<
	for(int i=1;i<=n+m;i++){
     
		int u = -1,mind = inf;//          
		for(int j = 1;j<=n+m;j++){
     
			if(!visited[j] && dis[j] < mind){
     
				u = j;
				mind = dis[j];
			}
		}
		if(u == -1)break;//       
		visited[u] = true;
		if(u <= n){
     
			tmpsum += mind;
		}
		if(u<=n && mind > range){
     //       
			isok = false;
			break;
		}else if (u<=n && mind < tmpmin){
     
			tmpmin = mind;
		}
		for(int k = 1;k <= n+m;k++){
     
			if(!visited[k] && dis[u]+graph[u][k] < dis[k]){
     
				dis[k] = dis[u]+graph[u][k];
			}
		} 
	}	
	if(isok){
     
		tmpsum /= (1.0*n);
		if(tmpmin > ansmin){
      //          
			ansid = s; 
			ansmin = tmpmin; //    。  
			ansave = tmpsum;
		}else if(tmpmin == ansmin){
     //       ，        
			if(tmpsum < ansave){
     
				ansid = s;
				ansmin = tmpmin;
				ansave = tmpsum;
			}
		}
	}
} 

int main(){
     
	//                   
	//         
	//              
	//      
	for(int i =0;i<=1020;i++){
     
		for(int j=0;j<1020;j++){
     
			graph[i][j] = inf;
		}
	}
	scanf("%d%d%d%d",&n,&m,&k,&range);
	//1-n    ，n+1~n+m    
	for(int i=0;i<k;i++){
     
		string a,b;
		int ta=0,tb=0,dis;
		cin>>a>>b>>dis;
		if(a[0]=='G') ta = n + stoi(a.substr(1));
		else ta = stoi(a);
		if(b[0]=='G') tb = n + stoi(b.substr(1));
		else tb = stoi(b);		
		graph[ta][tb] = graph[tb][ta] = min(graph[ta][tb],dis);//     
	} 
	for(int i=n+1;i<=n+m;i++){
     
		dijkstra(i);
	}
	if(ansid == -1){
     
		printf("No Solution
");
	}else{
     
		string id = "G"+to_string(ansid-n) ;
		cout<<id<<endl;
		printf("%0.1f %0.1f
",ansmin,ansave);
	}
	return 0;
}