L3-005. 垃圾箱分布

news/2024/7/8 4:14:51

L3-005. 垃圾箱分布

题目链接：https://www.patest.cn/contests/gplt/L3-005

Dijstra

与L2-001.紧急救援类似，是Dijstra最短路的拓展，要注意排序是按照：

1.到所有居民点的最小距离的最大；

2.平均距离最短；

3.编号最小.

代码如下：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<algorithm>
  5 #define N 1000
  6 #define M 10
  7 #define EPS 1e-8
  8 using namespace std;
  9 const int INF=0x3fffffff;
 10 int mp[N+M+1][N+M+1];
 11 int n,m,d;
 12 int Dis[M+1][N+M+1];
 13 bool out[N+M+1];
 14 struct res{
 15     double ave,mindis;
 16     int num;
 17     bool mark;
 18 };
 19 res r[11];
 20 int inti(char a[]);
 21 void dijstra(int x);
 22 bool compare(res a,res b){
 23     if(a.mindis!=b.mindis)
 24         return a.mindis>b.mindis;
 25     else{
 26         if(fabs(a.ave-b.ave)<EPS)
 27             return a.num<b.num;
 28         else
 29             return a.ave<b.ave;
 30     }
 31 }
 32 int main(void){
 33     //freopen("in.txt","r",stdin);
 34     int k;
 35     for(int i=1;i<=N+M;i++)
 36         for(int j=1;j<=N+M;j++)
 37             mp[i][j]=INF;
 38     scanf("%d%d%d%d",&n,&m,&k,&d);
 39     while(k--){
 40         char a[2][5];
 41         int b[2],dis;
 42         scanf("%s%s%d\n",a[0],a[1],&dis);
 43         for(int i=0;i<2;i++){
 44             if('1'<=a[i][0]&&a[i][0]<='9')
 45                 b[i]=inti(a[i]);
 46             else
 47                 b[i]=N+inti(&a[i][1]);
 48         }
 49         mp[b[0]][b[1]]=mp[b[1]][b[0]]=dis;
 50     }
 51     for(int i=1;i<=m;i++){
 52         for(int j=1;j<=N+m;j++)
 53             Dis[i][j]=INF;
 54         memset(out,1,sizeof(out));
 55         dijstra(i);
 56     }
 57     for(int i=1;i<=m;i++){
 58         r[i].mindis=INF;
 59         r[i].num=i;
 60         for(int j=1;j<=n;j++){
 61             if(Dis[i][j]!=INF){
 62                 if(Dis[i][j]>d)
 63                     r[i].mark=1;
 64                 if(r[i].mindis>Dis[i][j])
 65                     r[i].mindis=Dis[i][j];
 66                 r[i].ave+=Dis[i][j];
 67             }
 68         }
 69         r[i].ave/=n;
 70     }
 71     sort(&r[1],&r[1]+m,compare);
 72     bool flag=1;
 73     for(int i=1;i<=m;i++){
 74         if(r[i].mark)continue;
 75         printf("G%d\n",r[i].num);
 76         printf("%.1lf %.1lf\n",r[i].mindis,r[i].ave);
 77         flag=0;
 78         break;
 79     }
 80     if(flag)
 81         printf("No Solution\n");
 82     return 0;
 83 }
 84 int inti(char a[]){
 85     int len=strlen(a);
 86     int temp=0;
 87     for(int i=0;i<len;i++)
 88         temp=temp*10+(a[i]-'0');
 89     return temp;
 90 }
 91 void dijstra(int x){
 92     Dis[x][N+x]=0;
 93     while(1){
 94         int Min=INF,index;
 95         for(int i=1;i<=N+m;i++){
 96             if(out[i]&&Min>Dis[x][i]){
 97                 Min=Dis[x][i];
 98                 index=i;
 99             }
100         }
101         if(Min==INF)break;
102         out[index]=0;
103         for(int i=1;i<=N+m;++i){
104             if(out[i]&&Dis[x][index]+mp[index][i]<Dis[x][i])
105                 Dis[x][i]=Dis[x][index]+mp[index][i];
106         }
107     }
108 }