L3-005 垃圾箱分布

题目链接

总结下最后输出的要求：
①垃圾箱距离居民点“最短距离”最大的优先。
②在①相同的情况下，平均距离最小的优先。
③在②相同的情况下，编号小的优先。
都不符合则输出字符串。

本题的考点就是Dijkstra算法。
1、因此需要对输入的点进行预处理，已知居民点为N个，那么垃圾箱按顺序排到（N+1…N+2…N+M）即可；
2、对每个垃圾求单源最短路径；
3、根据Ds筛选符合条件的
4、自定义排序后输出

大家倒垃圾的时候，都希望垃圾箱距离自己比较近，但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，同时还要保证每个居民点都在距离它一个不太远的范围内。

现给定一个居民区的地图，以及若干垃圾箱的候选地点，请你推荐最合适的地点。如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。

输入样例1：
4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2
输出样例1：
G1
2.0 3.3

输入样例2：
2 1 2 10
1 G1 9
2 G1 20
输出样例2：
No Solution

#include<iostream>
#include<string>
#include<string.h>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
int N, M, K, D;
int map[1015][1015];		
int dist[1015];
bool vis[1015];
struct node {
    
	int num;
	int minn, sum;
};
vector<node> ans;
void dijkstra(int n) {
    
	memset(vis, false, sizeof(vis));
	memset (dist, 0x3f, sizeof(dist));
	int minn,t;
	vis[n] = true;
	for (int i = 1; i <= N + M; i++) {
    
		if (map[n][i] < 0x3f3f3f3f)	dist[i] = map[n][i];
	}
	for (int i = 1; i <= N +M; i++) {
    
		minn = 0x3f3f3f3f;
		for (int j = 1; j <= N +M; j++) {
    
			if (!vis[j] && minn > dist[j]) {
    
				minn = dist[j];
				t = j;
			}
		}
		vis[t] = true;
		for (int j = 1; j <= N +M; j++) {
    
			if (!vis[j] && dist[j] > dist[t] + map[t][j])
				dist[j] = dist[t] + map[t][j];
		}
	}
}
void check(int n) {
    
	int sum = 0;
	int minn = dist[1];
	node res;
	for (int i = 1; i <= N; i++) {
    
		if (dist[i] > D)	return;
		if (dist[i] < minn)	minn = dist[i];
		sum += dist[i];
	}
	res.num = n;
	res.sum = sum;
	res.minn = minn;
	ans.push_back(res);
}
bool cmp(node a, node b) {
    
	if (a.minn != b.minn)	return a.minn > b.minn;
	if (a.sum != b.sum)	return a.sum < b.sum;
	return a.num < b.num;
}
#define trans(s)(s[0]=='G'?stoi(s.substr(1))+N:stoi(s))
int main() {
    
	cin >> N >> M >> K >> D;
	memset(map, 0x3f, sizeof(map));
	string s1, s2;
	
	int x,y,z;
	for (int i = 0; i < K; i++) {
    
		cin >> s1 >> s2 >> z;
		x = trans(s1);
		y = trans(s2);
		map[x][y] = map[y][x] = z;
	}
	for (int i =1; i <=M; i++) {
    
		dijkstra(i+N);
		check(i);
	}
	if (ans.empty())	cout << "No Solution";
	else {
    
		sort(ans.begin(), ans.end(), cmp);
		cout <<"G" << ans.front().num << endl;
		printf("%.1f %.1f", 1.0*ans.front().minn,1.0*ans.front().sum/N);
	}
	return 0;
}