Skip to content

L3-005 垃圾箱分布

Statement

Metadata

  • 作者: 陈越
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 200 ms
  • 内存限制: 64 MB

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

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

输入格式

输入第一行给出4个正整数：N（\le 10^3）是居民点的个数；M（\le 10）是垃圾箱候选地点的个数；K（\le 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

Solution

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pid pair<int, db>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define N 10010
int n, m, k, Ds;
struct Graph {
    struct node {
        int to, nx, w;
        node() {}
        node(int to, int nx, int w) : to(to), nx(nx), w(w) {}
    } a[N << 1];
    int head[N], pos;
    void init() {
        memset(head, 0, sizeof head);
        pos = 0;
    }
    void add(int u, int v, int w) {
        a[++pos] = node(v, head[u], w);
        head[u] = pos;
        a[++pos] = node(u, head[v], w);
        head[v] = pos;
    }
} G;
#define erp(u) \
    for (int it = G.head[u], v = G.a[it].to, w = G.a[it].w; it; it = G.a[it].nx, v = G.a[it].to, w = G.a[it].w)

struct node {
    int to, w;
    node() {}
    node(int to, int w) : to(to), w(w) {}
    bool operator<(const node &other) const {
        return w > other.w;
    }
};
ll dist[N];
bool used[N];
void Dij(int st) {
    for (int i = 1; i <= n + m; ++i) {
        dist[i] = INF;
        used[i] = 0;
    }
    dist[st] = 0;
    priority_queue<node> pq;
    pq.push(node(st, 0));
    while (!pq.empty()) {
        int u = pq.top().to;
        pq.pop();
        if (used[u])
            continue;
        used[u] = 1;
        erp(u) if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            pq.push(node(v, dist[v]));
        }
    }
}

int read() {
    char s[10];
    scanf("%s", s);
    int tot = 0;
    int i;
    if (s[0] == 'G')
        i = 1;
    else
        i = 0;
    for (int len = strlen(s); i < len; ++i) tot = tot * 10 + (s[i] - '0');
    if (s[0] == 'G')
        tot += n;
    return tot;
}

int id;
ll total, Mindis;
void f(int now) {
    ll Max = 0, Min = INF, tot = 0;
    for (int i = 1; i <= n; ++i) {
        //		printf("%d %d %d\n", now, i, dist[i]);
        tot += dist[i];
        Max = max(Max, dist[i]);
        Min = min(Min, dist[i]);
    }
    if (Max > Ds)
        return;
    if (Min > Mindis) {
        id = now;
        total = tot;
        Mindis = Min;
    } else if (Min == Mindis && tot < total) {
        id = now;
        total = tot;
    }
}

int main() {
    // ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    G.init();
    scanf("%d%d%d%d", &n, &m, &k, &Ds);
    for (int i = 1, u, v, w; i <= k; ++i) {
        u = read();
        v = read();
        scanf("%d", &w);
        G.add(u, v, w);
    }
    Mindis = 0;
    total = INFLL;
    for (int i = 1; i <= m; ++i) {
        Dij(i + n);
        f(i);
    }
    if (total == INFLL)
        puts("No Solution");
    else {
        printf("G%d\n", id);
        printf("%.1f %.1f\n", Mindis * 1.0, total * 1.0 / n);
    }
    return 0;
}
Last update: May 4, 2022
Back to top