L3-005 垃圾箱分布

dijkstra。

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int distances[1010][1010];
int dis[1020],visited[1020];
int edges[1020][1020]; 
void dijkstra(int dis[],int visited[],int n,int s){//s起点 
	dis[s]=0;
	for(int i=1;i<=n;i++){
		int minv = inf,minx;
		for(int j=1;j<=n;j++){
			if(!visited[j]&&dis[j]<minv){
				minv=dis[j];
				minx=j;
			}
		}
		visited[minx]=1;
		for(int j=1;j<=n;j++){
			if(minv+edges[minx][j]<dis[j]){
				dis[j]=minv+edges[minx][j];
			}
		}
	}
}
int main(){
	memset(edges,0x3f,sizeof(edges));
	int n,m,k,ds;
	cin>>n>>m>>k>>ds;//居民点的个数 垃圾箱的个数 路径条数 最远不能超过 
    char s1[10],s2[10];
    int dist;
	for(int i=1;i<=k;i++){//输入 
		cin>>s1>>s2>>dist;
		int x = s1[0]=='G'?atoi(s1+1)+n:atoi(s1);
		int y = s2[0]=='G'?atoi(s2+1)+n:atoi(s2);
		edges[x][y]=edges[y][x]=dist;
	} 
	for(int i=1;i<=m;i++){
		memset(visited,0,sizeof(visited));
		memset(dis,0x3f,sizeof(dis));
		dijkstra(dis,visited,n+m,n+i);
		for(int j=1;j<=n;j++){
			distances[i][j]=dis[j];
		}
	}
	vector<int> res;
	int mins=0,path=inf; //到所有的居民点的最短距离中最长的那个
	for(int i=1;i<=m;i++){//第i个垃圾箱 
		int cmins=inf,cpath=0;
		int flag = 1;
		for(int j=1;j<=n;j++){
			if(distances[i][j]>ds){//这个垃圾桶不行 
				flag = 0;
				break;
			}
			cpath=cpath+distances[i][j];
			//更新最短距离
			cmins = min(distances[i][j],cmins); 
		}
		if(!flag) continue;
		if(cmins>mins){//更长 
             mins=cmins;//更新 
			 path=cpath; 
             res.clear();
             res.push_back(i);
		}else if(cmins==mins){
			//平均距离
			if(cpath<path) {
				res.clear();
				res.push_back(i);
				path=cpath;//更新 
			}
		}
	}
	if(res.size()==0){
		cout << "No Solution" << '\n';
	}else{
		cout << "G" << *res.begin() << '\n';
		printf("%.1f %.1f",(double)mins,(double)path/n);
	}
	return 0;
}

参考博客: http://www.manongjc.com/detail/52-kjhguymcxvgekvl.html