【CCCC】L3-005 垃圾箱分布 (30分)，Dijkstra跑n遍 = 多源最短路

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;//RE6

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]){//vis[jjjjjj],NotVVVVV
                dist[j] = dist[v]+e[v][j];
            }
        }
    }
}

int main(){
    //input
    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;
    }
    //对于每个垃圾桶，跑完dij后统计最短距离和平均距离
    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; //dist[jjjjjj],NotIIIIII
        }
        //更新答案
        lajitong tmp = lajitong{"G"+to_string(i),minds,aveds/n};
        //cout<<flag<<"\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;
}