[PAT解题报告] Gas Station
麻烦题，给定n个房间编号1-N, m个加油站，编号(N+1)-(N+m),
若干条路。加油站要合法，需要满足加油站到每个房间的距离都不超过一个给定的值D。
在合法的加油站里选出一个加油站，要求它到最近房间的距离尽可能小，如果相等，再让它到所有房间的平均距离尽可能小,如果还相等，要加油站的编号尽可能小。
分析： 只要加油站合法，选加油站就容易了。加油站合法不合法主要看加油站到每个房间的距离，所以对每个加油站来说就是个单源图的最短路。
我采用的是优先队列的办法算最短路。
大概框架如下：
优先队列里存 （点，距离）
先把（起点，0）入队。
每个点只有第一次出队是有效的，因为第一次出队时距离最小，我们允许重复入队和出队，就是重复出队时直接忽略就可以了。
然后扩展也很简单，当前点x第一次出队的时候，距离d[x]，是起点到x的最短距离，加一条边(x, y), 把(y, d[x] +
dist(x, y))入队，dist(x, y)表示(x,y)那条边的长度……
其实就是用优先队列做bfs而已。
代码：
#include <cstdio>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
priority_queue<pair<int,int> > q,qq;
int n,D;
vector<pair<int,int> > con[1024];
bool mark[1024];
int d[1024];
char s[100];
int get() {
int x;
if (s[0] == 'G') {
sscanf(s + 1, "%d", &x);
return n + x - 1;
}
sscanf(s, "%d", &x);
return x - 1;
}
void test(int from) {
q = qq;
q.push(make_pair(0, from));
memset(mark,0,sizeof(mark));
memset(d, 0xff,sizeof(d));
while (!q.empty()) {
int at = q.top().second;
int dis = q.top().first;
q.pop();
if (mark[at]) {
continue;
}
mark[at] = true;
d[at] = -dis;
if ((at < n) && (d[at] > D)) {
return;
}
for (int i = 0; i < con[at].size(); ++i) {
q.push(make_pair(dis - con[at][i].second, con[at][i].first));
}
}
}
int main() {
int m, e;
for (scanf("%d%d%d%d",&n,&m,&e,&D);e;--e) {
scanf("%s",s);
int x = get(), z;
scanf("%s%d",s,&z);
int y = get();
con[x].push_back(make_pair(y, z));
con[y].push_back(make_pair(x, z));
}
int besttotal = 2000000000, bestmin = -1, ind = -1;
for (int i = 0; i < m; ++i) {
test(n + i);
bool mark = true;
int maytotal = 0;
int maymin = 2000000000;
for (int j = 0; j < n; ++j) {
if ((d[j] > D) || (d[j] < 0)) {
mark = false;
break;
}
maytotal += d[j];
maymin = min(maymin, d[j]);
}
if (mark && ((ind < 0) || (bestmin < maymin) || ((bestmin == maymin) && (besttotal > maytotal)))) {
ind = i;
bestmin = maymin;
besttotal = maytotal;
}
}
if (ind >= 0) {
printf("G%d\n%.1lf %.1lf\n",ind + 1, bestmin * 1., besttotal * 1. / n);
}
else {
puts("No Solution");
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1072
