L3-005 垃圾箱分布 (30 分)

题目

题目链接

题解

对每个垃圾箱进行一次队列优化的Dijskra，每算出一个垃圾箱到其余各个居民点的最短距离后，计算这些距离中的最大距离、最短距离。如果最大距离大于要求的距离则直接忽略这个位置放垃圾桶的情况；否则，如果最短距离小于已经记录的最大的最短距离或者最短距离等于已经记录的最大的最短距离并且距离均值小于已经记录的最小均值，则更新要输出的信息。

优先级：

1. 最短距离要最大
2. 距离均值要最小
3. 垃圾桶编号要小（由于我们是顺序判断每种情况，所以不需要通过该条件进行更新）

注意：

直接printf("%.1lf")输出均值是过不了样例的，但是可以AC。

通过printf进行四舍五入会存在一些问题，这也是我在输出样例的时候发现的。

printf四舍五入问题

所以最好还是通过+0.5来处理

代码

#include
#define PII pair 
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 5e4 + 10;

int n, m, k, MAXDIST;
int best_pos, best_mindist = INF;
int maxmindist = -1; // 最大的最短距离 
int d[N];
int w[N], e[N], ne[N], h[N], idx;
double best_sum;

void add (int a, int b, int c) {
	w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void Dijkstra (int x) { // Dijkstra优先队列优化模板 
	
	memset (d, 0x3f, sizeof d);
	d[x] = 0;
	
	priority_queue  q;
	q.push ({0, x});
	
	while (q.size()) {
		PII tt = q.top ();
		q.pop ();
		int t = tt.second;
		int dist = tt.first;
		
		if (dist != d[t]) continue;
		
		for (int i = h[t];~i;i = ne[i]) {
			int j = e[i];
			if (d[j] > d[t] + w[i]) {
				d[j] = d[t] + w[i];
				q.push ({d[j], j});
			}
		}
	}	
}

int main()
{
	memset (h, -1, sizeof h);
	cin >> n >> m >> k >> MAXDIST;
	while (k --) {
		string a, b;
		int c;
		cin >> a >> b >> c;
		int aa, bb;
		if (a[0] == 'G') aa = atoi (a.substr(1).c_str()) + n; // 如果是垃圾箱就让编号从n+1开始 
		else aa = atoi (a.c_str());
		if (b[0] == 'G') bb = atoi (b.substr(1).c_str()) + n;
		else bb = atoi (b.c_str());
		add (aa, bb, c);
		add (bb, aa, c);
	}	
	
	for (int i = n+1;i