大家倒垃圾的时候&＃xff0c;都希望垃圾箱距离自己比较近&＃xff0c;但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方【此处为第一重排序选择的条件】&＃xff0c;同时还要保证每个居民点都在距离它一个不太远的范围内。
现给定一个居民区的地图&＃xff0c;以及若干垃圾箱的候选地点&＃xff0c;请你推荐最合适的地点。如果解不唯一&＃xff0c;则输出到所有居民点的平均距离最短的那个解【此处为第二重排序的原则】。如果这样的解还是不唯一&＃xff0c;则输出编号最小的地点【此处为第三重排序的原则&＃xff0c;尽管遍历的时候是按顺序的&＃xff0c;但sort排序的时候不是有序进行比较的&＃xff08;具体自己百度sort百度原理&＃xff09;&＃xff0c;所以比较加上这条&＃xff01;】。
输入格式&＃xff1a;
输入第一行给出4个正整数&＃xff1a;N&＃xff08;<&＃61; 103&＃xff09;是居民点的个数【在这里也WA了一次&＃xff0c;因为编号是123的时候就需要来一个while循环进行字符串转数字了】&＃xff1b;M&＃xff08;<&＃61; 10&＃xff09;是垃圾箱候选地点的个数&＃xff1b;K&＃xff08;<&＃61; 104&＃xff09;是居民点和垃圾箱候选地点之间的道路的条数&＃xff1b;DS是居民点与垃圾箱之间不能超过的最大距离【这里不用double来存贮其实也是可以过的&＃xff0c;WA了第六遍的时候我以为是数据超int了需要用double来存&＃xff0c;貌似是无用的】。所有的居民点从1到N编号&＃xff0c;所有的垃圾箱候选地点从G1到GM编号。
随后K行&＃xff0c;每行按下列格式描述一条道路&＃xff1a;
P1 P2 Dist
其中P1和P2是道路两端点的编号&＃xff0c;端点可以是居民点&＃xff0c;也可以是垃圾箱候选点。Dist是道路的长度&＃xff0c;是一个正整数。
输出格式&＃xff1a;
首先在第一行输出最佳候选地点的编号。然后在第二行输出该地点到所有居民点的最小距离和平均距离。数字间以空格分隔&＃xff0c;保留小数点后1位。如果解不存在&＃xff0c;则输出“No Solution”。
AC代码&＃xff1a;题目一般吧&＃xff0c;细节仔细都能考虑到的。
1 #include
2 #include
3 #include<string.h>
4 #include
5 #include
6 #include
7 #include<set>
8 #include
9 #include<string>
10 #include
11 #define inf 0x3f3f3f3f
12 #define dinf 0x7fffffff*1.0
13 using namespace std; //L3-005,垃圾箱&＃xff0c;16:50--
14 #define N 1200
15 #define ll long long
16 struct node{
17 int x;
18 double d;
19 node(int x&＃61;0,double d&＃61;0.0):x(x),d(d){}
20 };
21 struct node1{
22 int id;
23 double minn,ave;
24 node1(int id&＃61;0,double minn&＃61;-1,double ave&＃61;-1):id(id),minn(minn),ave(ave){}
25 }ans[12];
26 //1--到所有居民点的最短距离 相比较最长的地方,2-相等时&＃xff0c;按平均距离最短的那个解
27 bool cmp(node1 a,node1 b){
28 if(fabs(a.minn-b.minn)<1e-10){
29 if(fabs(a.ave-b.ave)<1e-10)
30 return a.id<b.id;
31 else
32 return a.ave<b.ave;
33 }
34 else
35 return a.minn>b.minn;
36 }
37 vector
38 double dis[N];
39 int vis[N];
40 int n,m,k;
41 double ds;//一个阈值
42 int cnt;
43 void debug(int num){
44 printf("gar:%d--",num);double s&＃61;0;
45 for(int i&＃61;1;i<&＃61;n&＃43;m;i&＃43;&＃43;){
46 s&＃43;&＃61;dis[i];
47 printf(" %.0lf",dis[i]);
48 }
49 cout<<" s: "<
50 }
51
52 void spfa(int ed){
53 queue<int>Q;
54 for(int i&＃61;1;i
55 dis[i]&＃61;dinf;
56 memset(vis,0,sizeof(vis));
57 Q.push(ed);
58 int u,v;
59 dis[ed]&＃61;0.0;
60
61 while(Q.size()>0){
62 u&＃61;Q.front();Q.pop();
63 vis[u]&＃61;0;
64 for(int i&＃61;0;i<(int)G[u].size();i&＃43;&＃43;){
65 v&＃61;G[u][i].x;
66 if(dis[v]>dis[u]&＃43;G[u][i].d){
67 dis[v]&＃61;dis[u]&＃43;G[u][i].d;
68 if(!vis[v]){
69 Q.push(v);
70 vis[v]&＃61;1;
71 }
72 }
73 }
74 }
75 double minn&＃61;dinf;
76 double sum&＃61;0.0;
77 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){
78 if(dis[i]>ds)return ;
79 sum&＃43;&＃61;dis[i];
80 minn&＃61;min(minn,dis[i]);
81 }
82 ans[&＃43;&＃43;cnt]&＃61;node1(ed,minn,sum/(1.0*n) );
83 }
84 int fact(char ch[]){
85 int x&＃61;0,i&＃61;0;
86 if(ch[0]&＃61;&＃61;&＃39;G&＃39;){
87 i&＃61;1;
88 }
89 while(ch[i]!&＃61;&＃39;\0&＃39;){
90 x &＃61;x*10&＃43;ch[i]-&＃39;0&＃39; ;
91 i&＃43;&＃43;;
92 }
93 if(ch[0]&＃61;&＃61;&＃39;G&＃39;)x&＃43;&＃61;n;
94 return x;
95 }
96 int main(){
97 char ch1[3],ch2[3];
98 while(scanf("%d%d%d%lf",&n,&m,&k,&ds)!&＃61;EOF){
99 for(int i&＃61;0;i
100 G[i].clear();
101 cnt&＃61;0;//统计加入ans结构体的个数
102 int x,y;
103 double dist;
104 for(int i&＃61;1;i<&＃61;k;i&＃43;&＃43;){
105 scanf("%s%s%lf",ch1,ch2,&dist);
106 x&＃61;fact(ch1);
107 y&＃61;fact(ch2);
108 G[x].push_back(node(y,dist));
109 G[y].push_back(node(x,dist));
110 }
111
112 for(int i&＃61;1&＃43;n;i<&＃61;n&＃43;m;i&＃43;&＃43;)
113 spfa(i);
114 if(cnt&＃61;&＃61;0){
115 printf("No Solution\n");
116 }
117 else{
118 sort(ans&＃43;1,ans&＃43;1&＃43;cnt,cmp);
119 printf("G%d\n",ans[1].id-n);
120 printf("%.1lf %.1lf\n",ans[1].minn,ans[1].ave);
121 }
122 }
123
124 return 0;
125 }
京公网安备 11010802041100号