PAT甲级1072.

A1072

题目

样例

样例1

输入:

输出:

G1
2.0 3.3

样例2

输入:

2 1 2 10
1 G1 9
2 G1 20

输出:

No Solution

思路和坑点

　　对每一个加油站，使用dijkstra算法求解单源最短距离，然后计算每一个加油站的各项要求指标，将符合的备选方案存放在数组中，按照要求排序输出符合最终结果的一个。
　　坑点:
　　读入数据的时候要区分居民点和加油站，需要把加油站映射成为图中的顶点。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define MAXV 1015
#define INF 0x3fffffff

typedef struct gas{                                        //加油站结构体 
    string id;                                            //id 
    int mindis;                                            //到城市的最短距离 
    double ad;                                            //到城市的平均距离 
}Gas;
typedef struct node{                                    //邻接表储存图 
    int v,w;
    node(int _v,int _w):v(_v),w(_w){}
}Node;
vector<Node> G[MAXV];
vector<Gas> gasout;                                        //保存符合条件的加油站
bool vis[MAXV];                                            //访问标记数组 
int n,m,k,d;                                            
void D(int s);                                            //Dijkstra求单源最短路径 
void getdis(int &a,int &b,int &c);                        //读取一条边的信息 
bool cmp(Gas a,Gas b){                                    //对答案进行排序
    if(a.mindis!=b.mindis)    return a.mindis>b.mindis;    //按照最小距离尽可能远 
    else if(a.ad!=b.ad)        return a.ad<b.ad;            //按照平均距离尽可能小 
    else                     return a.id<b.id;            //按照编号尽可能小 
}
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    scanf("%d%d%d%d",&n,&m,&k,&d);
    for(int i=0;i<k;i++){
        int a,b,c;
        getdis(a,b,c);                                    //读入一条边信息 
        G[a].push_back(node(b,c));                        //构建图 
        G[b].push_back(node(a,c));
    }
    for(int i=1;i<=m;i++){                                //对每一个加油站求解单源最短路径 
        D(n+i);
    }
    if(gasout.size()==0)    puts("No Solution");        //如果没有答案 
    else{
        sort(gasout.begin(),gasout.end(),cmp);            //排序后输出第一个 
        cout<<gasout[0].id;
        printf("\n%.1f %.1f",gasout[0].mindis*1.0,gasout[0].ad);
    }
    
    return 0;    
}
void D(int s)
{
    int dis[MAXV];
    fill(dis,dis+MAXV,INF);
    fill(vis,vis+MAXV,false);
    dis[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&&dis[j]<MIN){
                u=j;
                MIN=dis[j];
            }
        }
        if(u==-1) return;
        vis[u]=true;
        for(int j=0;j<G[u].size();j++){
            int v=G[u][j].v;
            if(vis[v]==false&&dis[u]+G[u][j].w<dis[v]){
                dis[v]=dis[u]+G[u][j].w;
            }
        }
    }
    double sum=0;
    int min=INF;
    for(int i=1;i<=n;i++){                                //统计加油站和居民住房的关系值 
        if(dis[i]>d)                                    //如果到居民距离超过服务距离，不能入选 
            return;
        sum+=dis[i]; 
        min=dis[i]<min?dis[i]:min;
    }
    int index=s-n;                                        //如果满足选择要求，加入最后的答案数组中 
    string id="G";
    if(index==10)    id="G10";                            //G10比较特殊，单独处理 
    else id.push_back('0'+index);
    Gas isok;
    isok.id=id;
    isok.ad=sum/n;
    isok.mindis=min;
    gasout.push_back(isok);
}
void getdis(int &a,int &b,int &c)
{
    string st1,st2,st3;
    cin>>st1>>st2>>st3;                                    //按照字符串读入 
    if(st1[0]=='G'){                                    //如果是加油站，映射成结点n+i 
        string temp=st1.substr(1,st1.size()-1);
        sscanf(temp.c_str(),"%d",&a);
        a+=n;
    }
    else
        sscanf(st1.c_str(),"%d",&a);                    //如果是居民楼，直接映射成结点 
    if(st2[0]=='G'){
        string temp=st2.substr(1,st2.size()-1);
        sscanf(temp.c_str(),"%d",&b);
        b+=n;
    }
    else
        sscanf(st2.c_str(),"%d",&b);
    sscanf(st3.c_str(),"%d",&c);
}

PAT_A1072

目录

A1072

题目

样例

样例1

样例2

思路和坑点

AC代码

SAquarius