problem
L3-005 垃圾箱分布 (30分) 大家倒垃圾的时候，都希望垃圾箱距离自己比较近，但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，同时还要保证每个居民点都在距离它一个不太远的范围内。
现给定一个居民区的地图，以及若干垃圾箱的候选地点，请你推荐最合适的地点。如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。
输入格式： 输入第一行给出4个正整数：N（≤10 3 ）是居民点的个数；M（≤10）是垃圾箱候选地点的个数；K（≤10 4 ）是居民点和垃圾箱候选地点之间的道路的条数；D S 是居民点与垃圾箱之间不能超过的最大距离。所有的居民点从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
给定一张图，n个居民点(1e3)，m个垃圾点(10)，k条边(1e4)。求选一个垃圾点，满足以下条件到所有居民点距离不超过DS（大家都需要垃圾箱）到所有居民点最短距离最长（谁都不想住垃圾箱旁边），同时平均距离尽可能短（大家都需要垃圾箱）
solution
从每个垃圾点开始遍历，每个点跑一次Dijkstra，复杂度O（10*nlogn）dist数组统计到所有居民点的距离，统计最短距离，平均距离，判断DS。维护更新最小的ans输入垃圾站字符编号问题，用数字+n处理
#include<bits/stdc++.h>
using namespace std
;
const int maxn
= 1050;
int n
, m
, k
, ds
;
struct lajitong
{
string id
;
double minds
, aveds
;
bool operator < (const lajitong
&b
){
if(minds
!= b
.minds
)return minds
>b
.minds
;
if(aveds
!= b
.aveds
)return aveds
<b
.aveds
;
return id
< b
.id
;
}
};
int e
[maxn
][maxn
], dist
[maxn
], vis
[maxn
];
void Dijkstra(int u
){
memset(dist
,0x3f,sizeof(dist
));
memset(vis
,0,sizeof(vis
));
dist
[u
] = 0;
for(int i
= 1; i
<= n
+m
; i
++){
int v
= -1, _min
= (1e9);
for(int j
= 1; j
<= n
+m
; j
++)
if(!vis
[j
] && dist
[j
]<_min
)
{_min
= dist
[j
]; v
= j
;}
if(v
==-1)return ;
vis
[v
] = 1;
for(int j
= 1; j
<= n
+m
; j
++){
if(!vis
[j
] && dist
[j
]>dist
[v
]+e
[v
][j
]){
dist
[j
] = dist
[v
]+e
[v
][j
];
}
}
}
}
int main(){
cin
>>n
>>m
>>k
>>ds
;
memset(e
,0x3f,sizeof(e
));
for(int i
= 0; i
< k
; i
++){
char a
[10], b
[10]; int c
;
scanf("%s%s%d",a
,b
,&c
);
int aa
= (a
[0]=='G' ? n
+atoi(&a
[1]) : atoi(a
));
int bb
= (b
[0]=='G' ? n
+atoi(&b
[1]) : atoi(b
));
e
[aa
][bb
] = e
[bb
][aa
] = c
;
}
lajitong ans
;
for(int i
= 1; i
<= m
; i
++){
Dijkstra(n
+i
);
double aveds
= 0, minds
= dist
[1];
int flag
= 1;
for(int j
= 1; j
<= n
; j
++){
aveds
+= dist
[j
];
minds
= min(minds
, dist
[j
]*1.0);
if(dist
[j
]>ds
)flag
= 0;
}
lajitong tmp
= lajitong
{"G"+to_string(i
),minds
,aveds
/n
};
if(flag
&& (ans
.id
.empty() || tmp
<ans
)){
ans
= tmp
;
}
}
if(ans
.id
.empty())
cout
<<"No Solution"<<endl
;
else
printf("%s\n%.1lf %.1lf", ans
.id
.c_str(), ans
.minds
, ans
.aveds
);
return 0;
}
