大家倒垃圾的时候，都希望垃圾箱距离自己比较近，但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，同时还要保证每个居民点都在距离它一个不太远的范围内。
现给定一个居民区的地图，以及若干垃圾箱的候选地点，请你推荐最合适的地点。如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。
输入格式： 输入第一行给出4个正整数：N（≤103）是居民点的个数；M（≤10）是垃圾箱候选地点的个数；K（≤104 ）是居民点和垃圾箱候选地点之间的道路条数；DS是居民点与垃圾箱之间不能超过的最大距离。所有的居民点从1到N编号，所有的垃圾箱候选地点从G1到GM编号。
随后K行，每行按下列格式描述一条道路：
P1 P2 Dist 其中P1和P2是道路两端点的编号，端点可以是居民点，也可以是垃圾箱候选点。Dist是道路的长度，是一个正整数。
输出格式： 首先在第一行输出最佳候选地点的编号。然后在第二行输出该地点到所有居民点的最小距离和平均距离。数字间以空格分隔，保留小数点后1位。如果解不存在，则输出No Solution。
输入样例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
思路：板子题，m次dijkstra,注意是无向图
#include <bits/stdc++.h> #include <string> using namespace std; const int maxv = 1020; const int INF = 1e9; int N, M, K, Ds;//N+M总点数，K边数 int m = K, G[maxv][maxv]; int d[maxv]; bool vis[maxv]; struct Node{ int id; double d_min; double aver; }ans[maxv]; bool cmp(Node a, Node b){ if(a.d_min != b.d_min){ return a.d_min > b.d_min;//最短距离最长 }else{ if(a.aver != b.aver) return a.aver < b.aver; else return a.id < b.id; } } void Dijkstra(int s){ fill(d, d+maxv, INF); fill(vis, vis+maxv, 0); d[s] = 0; for(int i = 0; i <= N+M; i++){ int u = -1, Min = INF; //找到最短路径的下一点 for(int j = 1; j <= N+M; j++){ if(!vis[j] && d[j] < Min){ u = j; Min = d[j]; } } if(u == -1) return; vis[u] = true; //更新d[] for(int v = 1; v <= N+M; v++){ if(vis[v] == false && G[u][v] != INF && d[v] > d[u]+G[u][v]){ d[v] = d[u]+G[u][v]; } } } } int change(string s){ if(s[0] == 'G'){ s.erase(0,1); int id = 0; stringstream ss(s); ss >> id; return id+N; }else{ int id = 0; stringstream ss(s); ss >> id; return id; } } int main(){ cin >> N >> M >> K >> Ds; string str1, str2; int w; fill(G[0], G[0]+ maxv*maxv , INF); for(int i = 0; i < K; i++){ cin >> str1 >> str2 >> w; int id1 = change(str1); int id2 = change(str2); G[id1][id2] = w; G[id2][id1] = w; } int cnt = 0; for(int i = N+1; i <= N+M; i++){ Dijkstra(i); bool flag = false; int sum = 0,t_min = INF; for(int j = 1; j <= N; j++){ sum += d[j]; t_min = min(t_min, d[j]); if(d[j] > Ds){ flag = true; break; } } if(flag == false){ ans[cnt].id = i; ans[cnt].d_min = t_min; ans[cnt++].aver = sum*1.0/N; //cout << i <<" "<< t_min << " "<<sum*1.0/N << endl; } } if(cnt == 0){ cout << "No Solution" << endl; }else{ sort(ans, ans+cnt,cmp); stringstream a; a << ans[0].id-N; cout << "G" << a.str() << endl; cout << fixed << setprecision(1) << ans[0].d_min+1e-8 <<" "<< ans[0].aver+1e-8 << endl;//保留一位小数 } return 0; }上面代码复杂度为：O(n^2) 我们最好使用堆优化（就是优先队列）
