⭐⭐⭐⭐⭐PAT A1072 Gas Station

题目描述

题目链接

从m个加油站里面选取1个站点，让他离居民区的最近的距离是m中最远的，并且没有超出服务范围ds之内。如果有很多个最远的加油站，输出距离所有居民区距离平均值最小的那个。如果平均值还是一样，就输出按照顺序排列加油站编号最小的那个

知识点

Dijkstra单源最短路径

实现

码前思考

1. 这道题目，我看题目看了半天，才理解了

   A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible.

   这个条件的含义，也就是最近的那个点要最远，可能是安全考虑吧；

2. 由于昨天刚刚学了Dijkstra的堆优化版本，所以这次打算使用堆优化版本的，但是好像一般机试里面裸的Dijkstra就可以解决问题了；

3. 之前有想对Dijksta进行剪枝，但是写错了，后来直接进行暴力，发现也是可以通过的，但是我不知道自己剪枝错在哪里了。

代码实现

下面是传统DIjkstra，参考柳神的代码：

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int inf = 999999999;
int n, m, k, ds, station;
int e[1020][1020], dis[1020];
bool visit[1020];
int main() {
    fill(e[0], e[0] + 1020 * 1020, inf);
    for (int i = 0; i < 1020; i++) e[i][i] = 0;
    fill(dis, dis + 1020, inf);
    scanf("%d%d%d%d", &n, &m, &k, &ds);
    for(int i = 0; i < k; i++) {
        int tempdis;
        string s, t;
        cin >> s >> t >> tempdis;
        int a, b;
        if(s[0] == 'G') {
            s = s.substr(1);
            a = n + stoi(s);
        } else {
            a = stoi(s);
        }
        if(t[0] == 'G') {
            t = t.substr(1);
            b = n + stoi(t);
        } else {
            b = stoi(t);
        }
        e[a][b] = e[b][a] = tempdis;
        e[a][b] = e[b][a] = min(tempdis, e[a][b]);
    }
    int ansid = -1;
    double ansdis = -1, ansaver = inf;
    for(int index = n + 1; index <= n + m; index++) {
        double mindis = inf, aver = 0;
        fill(dis, dis + 1020, inf);
        fill(visit, visit + 1020, false);
        dis[index] = 0;
        for(int i = 0; i < n + m; i++) {
            int u = -1, minn = inf;
            for(int j = 1; j <= n + m; j++) {
                if(visit[j] == false && dis[j] < minn) {
                    u = j;
                    minn = dis[j];
                }
            }
            if(u == -1) break;
            visit[u] = true;
            for(int v = 1; v <= n + m; v++) {
                if(visit[v] == false && dis[v] > dis[u] + e[u][v])
                    dis[v] = dis[u] + e[u][v];
            }
        }
        for(int i = 1; i <= n; i++) {
            if(dis[i] > ds) {
                mindis = -1;
                break;
            }
            if(dis[i] < mindis) mindis = dis[i];
            aver += 1.0 * dis[i];
        }
        if(mindis == -1) continue;
        aver = aver / n;
        if(mindis > ansdis) {
            ansid = index;
            ansdis = mindis;
            ansaver = aver;
        } else if(mindis == ansdis && aver < ansaver) {
            ansid = index;
            ansaver = aver;
        }
    }
    if(ansid == -1)
        printf("No Solution");
    else
        printf("G%d\n%.1f %.1f", ansid - n, ansdis, ansaver);
    return 0;
}

下面是Dijkstra+堆优化

//使用堆优化进行 
#include <cstdio>
#include <iostream>
#include <vector>
#include <string> 
#include <algorithm>
#include <queue>
using namespace std; 
const int maxn = 1e4;
const int INF = 0x3fffffff;
 
struct node{
	int v;
	int cost;
	node(){};
	node(int _v,int _cost):v(_v),cost(_cost){}
	//路径越短优先级越高 
	friend bool operator < (node a,node b){
		return a.cost > b.cost;
	} 
};

int N;
int M;
int K;
int Ds;
vector<node> adj[maxn];
bool vis[maxn];
int d[maxn];
int ansDis; 
int ansId;
double ansAvg;
 
void Dijkstra(int s){
	//进行初始化
	fill(vis,vis+maxn,false);
	fill(d,d+maxn,INF);
	d[s+N] = 0;
	
	//建立一个priority_queue
	priority_queue<node> q;
	q.push(node(s+N,0));
	
	//优先队列不为空 
	//堆优化Dijkstra模板 
	while(!q.empty()){
		//每次找最小的 
		int u =  q.top().v;
		int cost = q.top().cost;
		q.pop();
		
		//如果已经被访问过了，这里需要注意！ 
		if(vis[u] == true){
			continue;
		}
		
		vis[u] = true;
	
		//接下来进行更新
		for(int j=0;j<adj[u].size();j++){
			int v = adj[u][j].v;
			int cost = adj[u][j].cost;
			if(vis[v] == false && d[u]+cost < d[v]){
				q.push(node(v,d[u]+cost));
				d[v] = d[u]+cost;
			}
		} 	 
	}
	
	int curMin = INF; 
	int total=0;
	//从1开始编号的 
	//接下来进行检查题中的各项条件
	for(int i=1;i<=N;i++){
		//如果出现距离大于DS的直接返回
		if(d[i] > Ds){//内含了孤立点的情况 
			return;
		}else{
			//寻找最小的那一个
			curMin = min(curMin,d[i]); 
			total += d[i];
		}	
	}
	double curAvg = (1.0*total)/N;
	 
	
	//然后判断最小的是否大于最小的
	if(curMin > ansDis){
		ansDis = curMin;
		ansId = s;
		ansAvg = curAvg;
	}else if(curMin == ansDis){
		//则进行平均值比较
		if(curAvg < ansAvg){
			ansDis = curMin;
			ansId = s;
			ansAvg = curAvg;			
		} 
	} 
}

int main(){
	scanf("%d %d %d %d",&N,&M,&K,&Ds);
	//保存最短距离 
	ansDis = -INF;
	ansId = -1;
	ansAvg = INF;
	
	for(int i=0;i<K;i++){		
		//以string作为读入更好~
		string a,b;
		int cost;
		cin>>a>>b>>cost;
		int u,v;
		
		if(a[0] != 'G'){
			u = stoi(a);
		}else{
			u = N + stoi(a.substr(1));
		}
		if(b[0] != 'G'){
			v = stoi(b);
		}else{
			v = N + stoi(b.substr(1));
		}
		adj[u].push_back(node(v,cost));
		adj[v].push_back(node(u,cost)); 
	}
	
	//接下来进行遍历
	//注意下标 
	for(int i=1;i<=M;i++){
		Dijkstra(i);
	}
	
	if(ansId == -1){
		printf("No Solution\n");
	}else{
		printf("G%d\n",ansId);
		printf("%.1f %.1f\n",ansDis*1.0,ansAvg);		
	}
	 
	return 0;
}

码后反思

1. 在输入数据的时候，我有两个细节错误：
   1. 对于gas station的判断，我居然使用的是string的长度是不是1，应该是判断G才对！
   2. 对于substr()可以直接传入开始位置，不传入长度，表示取接下来的所有子串；
2. 对于C++的浮点数四舍五入运算，%.1f会存在下面这个问题，但是貌似直接这样写，提交上去也是对的。。。
   
3. 对于堆优化的Dijkstra，它并没有比普通Dijkstra少任何数据结构，相反还多了一个priority_queue，而且会压队列很多重复的v（但是cost值不一样），所以每次出队的时候，都要去判断是否已访问，访问过就跳过去continue；
4. 注意，题中对gas station的编号是在N之后编号就行，不要使用1000；
5. 注意一下priority_queue里面的比较函数怎么写。