PAT甲级-1072 Gas Station (30分)(迪杰斯特拉算法即可,DFS会超时)
发布日期:2022-02-10 08:10:57 浏览次数:4 分类:技术文章

本文共 3449 字,大约阅读时间需要 11 分钟。

题目:
分析:路径问题,用DFS会超时,使用迪杰斯特拉得出dis数组即可。注意!!!有个小坑:station不只是1-9,有可能是两位数以上,10,11,等等,因此在输入的时候字符串的处理要注意,不然最后一个测试点会报错。

AC代码(dj):

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define MAX 999999999typedef long long ll;using namespace std;int n,m,k,ds;double road[10020][10020];int visi[10020];double dis[10020];//1-1000 1001-1010//每个候选加油站的距离住宅的所有最小中选一个最大的//必须保证所有住宅在加油站的服务范围//有多个选择的话,选平均距离到住宅最小的,还有多个选序号最小的void dj(int root){ 
              
   fill(dis,dis+10020,MAX);
dis[root] = 0;
for(int i = 1; i <= n+m ;i++)
{
   int u = -1;
int mm = MAX;
for(int j = 1;j<=n+m;j++)
{
   if(dis[j] < mm && !visi[j])
{
   u = j;
mm = dis[j];
}
}
visi[u] = 1;
for(int j = 1;j <= n+m;j++)
{
   if(!visi[j] && road[u][j] != 0 && dis[u] + road[u][j] < dis[j])
dis[j] = dis[u] +road[u][j];
}
}}int main(){
   cin>>n>>m>>k>>ds;
for(int i = 1;i<=k;i++)
{
   string a,b;
int x,y;
double c;
cin>>a>>b>>c;
if(a[0] == 'G')
x = n + stoi(a.substr(1,a.size()-1));
else
x = stoi(a);
if(b[0] == 'G')
y = n + stoi(b.substr(1,b.size()-1));
else
y = stoi(b);
road[x][y] = road[y][x] = c;
}
int idx = -1;
double max_dis = -1;
double avg_dis ;
for(int i = n + 1;i <= n + m;i++)
{
   int flag = 0;
fill(visi,visi+10020,0);
double c_avg_dis = 0;
double min_dis = MAX;
dj(i);
for(int j = 1;j<=n;j++){
   c_avg_dis += dis[j];
if(dis[j] < min_dis)
min_dis = dis[j];
if(dis[j] > ds)
flag = 1;
}
if(flag)
continue;//超出服务范围
if(min_dis > max_dis) {
   max_dis = min_dis;
avg_dis = c_avg_dis;
idx = i;
}
else if(min_dis == max_dis && c_avg_dis < avg_dis)
{
   avg_dis = c_avg_dis;
idx = i;
}
}
if(idx == -1) {
   cout<<"No Solution";
return 0;
}
cout<<"G"< <
printf("%.1f %.1f",max_dis*1.0, avg_dis/n);
return 0;}

超时代码(DFS):

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #define MAX 999999999typedef long long ll;using namespace std;int n,m,k,ds;double road[10020][10020];int visi[10020];double dis[10020];//1-1000 1001-1010//每个候选加油站的距离住宅的所有最小中选一个最大的//必须保证所有住宅在加油站的服务范围//有多个选择的话,选平均距离到住宅最小的,还有多个选序号最小的double max_dis = -1;double avg_dis;double min_dis = MAX;double c_dis;void dfs(int root){ 
             
   visi[root] = 1;
if(c_dis < min_dis && c_dis != 0 && root >=1 && root <= n)//找出当前加油站距离最近的一个住宅的距离
min_dis = c_dis;
if(c_dis < dis[root] && c_dis != 0 && root >=1 && root <= n)//得出dis数组的值,为距离每个住宅的最近距离
dis[root] = c_dis;
for(int i = 1;i <= n + m;i++)
{
   if(!visi[i] && road[root][i] != 0)
{
   c_dis += road[root][i];
dfs(i);
c_dis -= road[root][i];
}
}
visi[root] = 0;}int main(){
   cin>>n>>m>>k>>ds;
for(int i = 1;i<=n;i++)
dis[i] = MAX;
for(int i = 1;i<=k;i++)
{
   string a,b;
int x,y;
double c;
cin>>a>>b>>c;
   
if(a[0] == 'G')
x = n + stoi(a.substr(1,a.size()-1));
else
x = stoi(a);
if(b[0] == 'G')
y = n + stoi(b.substr(1,b.size()-1));
else
y = stoi(b);
road[x][y] = road[y][x] = c;
}
int idx =-1;
for(int i = n + 1;i <= n + m;i++)
{
   fill(dis+1,dis+1+n,MAX);
int flag = 0;
double c_avg_dis = 0;
min_dis = MAX;
dfs(i);
for(int j = 1;j<=n;j++){
   c_avg_dis += dis[j];
if(dis[j] > ds)
flag = 1;
}
if(flag)
continue;//超出服务范围
if(min_dis > max_dis) {
   max_dis = min_dis;
avg_dis = c_avg_dis;
idx = i;
}
else if(min_dis == max_dis && c_avg_dis < avg_dis)
{
   avg_dis = c_avg_dis;
idx = i;
}
}
if(idx == -1) {
   cout<<"No Solution";
return 0;
}
cout<<"G"< <
printf("%.1f %.1f",max_dis*1.0, avg_dis/n);
return 0;}

转载地址:https://blog.csdn.net/qq_43567222/article/details/113482775 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:word使用
下一篇:PAT甲级-1073 Scientific Notation (20 分)

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.191.171.16]2022年08月18日 11时17分27秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章