PAT天梯赛L3-005 垃圾箱分布-白红宇

PAT天梯赛L3-005 垃圾箱分布

阅读量：5162 次

发布时间：2019-06-13

本文共 2746 字，大约阅读时间需要 9 分钟。

题目链接：

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

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

输入格式：

输入第一行给出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 51 2 21 4 21 G1 41 G2 32 3 22 G2 13 4 23 G3 24 G1 3G2 G1 1G3 G2 2

输出样例1：

G12.0 3.3

输入样例2：

2 1 2 101 G1 92 G1 20

输出样例2：

No Solution

思路：一眼看去，用floyd？？但是又不好处理，（垃圾箱是字符）。可以把垃圾箱的编号往n后面继续排。后来看了题解。

AC代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int MAX = 2000;//1010段错误。。。。。题目明明说的1000.。。坑！！！！！！！！！！！！！！！！const int INF = 0X3f3f3f;struct node{ int v; int dis; node() {} node(int _v, int _dis) : v(_v), dis(_dis) {}};vector
              
                G[MAX];int d[MAX];int n, m, k, ds;int ansminid = -1; double ansminaver = INF, ansmindis = -1;void dijkstra(int s) {//处理每一个垃圾站 bool vis[MAX] = {false}; fill(d, d + MAX, INF); double tempminaver = 0, tempmindis = INF;//我开成了int d[s] = 0; for(int i = 1; i <= n + m; i++) { int u = -1, MIN = INF; for(int j = 1; j <= n + m; j++) { if(vis[j] == false && d[j] < MIN) { u = j; MIN = d[j]; } } if(u == -1) break; vis[u] = true; for(int j = 0; j < G[u].size(); j++) { int v = G[u][j].v; if(vis[v] == false && d[v] > d[u] + G[u][j].dis) d[v] = d[u] + G[u][j].dis; } } for(int i = 1; i <= n; i++) {//找最小值 求平均距离 if(d[i] > ds) { tempmindis = -1;//超出范围 break; } if(d[i] < tempmindis) { tempmindis = d[i]; } tempminaver += 1.0 * d[i]; } if(tempmindis == -1) return;//超出范围的特判 tempminaver = tempminaver / n; if(tempmindis > ansmindis) { ansmindis = tempmindis; ansminid = s; ansminaver = tempminaver; } else if(tempmindis == ansmindis && tempminaver < ansminaver) { // 第二准则 第三准则由于是有序处理 所以默认 ansminid = s; ansminaver = tempminaver; }}int main() { cin >> n >> m >> k >> ds; int u, v, w; string s1, s2; while(k--) {//由于输入不确定 只能以字符串输入 然后灵活变化 cin >> s1 >> s2 >> w; if(s1[0] == 'G') {//此处用了stoi函数 和 substr函数 很巧妙 u = n + stoi(s1.substr(1));//注意不要写stoi（s1[1]); } else u = stoi(s1); if(s2[0] == 'G') { v = n + stoi(s2.substr(1)); } else v = stoi(s2); G[u].push_back(node(v, w)); G[v].push_back(node(u, w)); } for(int i = n + 1; i <= n + m; i++) dijkstra(i); if(ansminid == -1) { cout << "No Solution"; } else { cout << "G" << ansminid - n << endl; printf("%.1lf %.1lf", ansmindis, ansminaver); } return 0;}

转载于:https://www.cnblogs.com/ACMerszl/p/9573002.html

你可能感兴趣的文章