1072. Gas Station (30)
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. However it must guarantee that all the houses are in its service range.
Now given the map of the city and several candidate locations for the gas station, you are supposed to give the best recommendation. If there are more than one solution, output the one with the smallest average distance to all the houses. If such a solution
is still not unique, output the one with the smallest index number.
Input Specification:
Each input file contains one test case. For each case, the first line contains 4 positive integers: N (<= 103), the total number of houses; M (<= 10), the total number of the candidate locations for the gas stations; K (<= 104),
the number of roads connecting the houses and the gas stations; and DS, the maximum service range of the gas station. It is hence assumed that all the houses are numbered from 1 to N, and all the candidate locations are numbered
from G1 to GM.
Then K lines follow, each describes a road in the format
P1 P2 Dist
where P1 and P2 are the two ends of a road which can be either house numbers or gas station numbers, and Dist is the integer length of the road.
Output Specification:
For each test case, print in the first line the index number of the best location. In the next line, print the minimum and the average distances between the solution and all the houses. The numbers in a line must be separated by a space and be accurate up to
1 decimal place. If the solution does not exist, simply output “No Solution”.
Sample Input 1:
4 3 11 5 1 2 2 1 4 2 1 G1 4 1 G2 3 2 3 2 2 G2 1 3 4 2 3 G3 2 4 G1 3 G2 G1 1 G3 G2 2
Sample Output 1:
G1 2.0 3.3
Sample Input 2:
2 1 2 10 1 G1 9 2 G1 20
Sample Output 2:
No Solution
题意
给出一个图，其中有 N <= 103 个节点是居民房，M
<= 10 个节点是计划建造加油站的候选点。给出加油站所能服务的最远距离 D。要求计算出合适的位置建造加油站，满足如下优先级条件：
- 所有居民房必须在加油站的服务距离内。
- 所有居民房中距离加油站的最近的居民房与加油站之间的距离是最远的。（大概是安全方面的考虑，加油站要离居民区远一点）
- 所有房间距离加油站的最小距离的总和最小。（节约居民加油的总体成本）
- 同等条件下，序号越小的加油站优先。
分析
实际上是求加油站到所有点的最短路径的问题，使用 Dijsktra 可以满足。
另外，需要考虑求最短路径的过程中是否要将其他加油站所构建的路径算入在内
代码
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iomanip>
using namespace std;
//此代码使用前，需删除下面两行+后面的system("PAUSE")
ifstream fin("in.txt");
#define cin fin
struct Res{
int index;
int mm;
int sum;
Res(int i,int m,int s):index(i),mm(m),sum(s){}
};
const int INF = 0x7fffffff;
const int NUM = 1000+10+2;
int dis[NUM][NUM]={0};
int minDis[11][NUM]={0};
int n,m,k,ds;
bool visited[NUM];
int calcIndex(const char p[]){
if(p[0]=='G'){
return n+p[1]-'0';
}else{
return p[0]-'0';
}
}
void Dijkastra(int centre){
memset(visited,false,sizeof(bool)*NUM);
int cur = n+1+centre;
int i,next,count,t;
int mm;
count = 0;
while(count < n+m-1) //前提是 图为整个连通图
{
visited[cur] = true;
mm = INF;
for(i=1;i<n+m+1;i++){
if(visited[i])continue;
if(dis[cur][i]){ //若节点cur到i存在通路
t = minDis[centre][cur] + dis[cur][i];
if(t < minDis[centre][i] || minDis[centre][i]==0){
minDis[centre][i] = t; //更新centre到i的最短路径值
}
}
if(minDis[centre][i] < mm && minDis[centre][i]!=0){
mm = minDis[centre][i];
next = i;
}
}
cur = next;
minDis[centre][cur] = mm;
count ++;
}
}
bool cmp(const Res& aa,const Res& bb){
if(aa.mm != bb.mm){
return aa.mm > bb.mm;
}else if(aa.sum != bb.sum){
return aa.sum < bb.sum;
}else{
return aa.index < bb.index;
}
}
int main()
{
cin>>n>>m>>k>>ds;
int i;
char p1[3],p2[3];
int index1,index2;
for(i=0;i<k;i++){
cin>>p1>>p2;
index1 = calcIndex(p1);
index2 = calcIndex(p2);
cin>>dis[index1][index2];
dis[index2][index1] = dis[index1][index2];
}
int j;
int mm,sum;
vector<Res> vec;
for(i=0;i<m;i++){
Dijkastra(i); //以加油站i为源点，进行最短路径遍历
mm = INF;
sum = 0;
bool isOK = true;
for(j=1;j<n+1;j++){
if(minDis[i][j] > ds){ //若加油站距居民 距离超出 服务范围，直接pass掉这个方案
isOK = false;
break;
}else{
sum += minDis[i][j];
if(minDis[i][j] < mm) mm = minDis[i][j];
}
}
if(isOK)vec.push_back(Res(i,mm,sum));
}
if(vec.size()==0){
cout<<"No Solution"<<endl;
}else{
sort(vec.begin(),vec.end(),cmp); //排序，规则①最短距离mm最大②距离和sum最小③序号index最小
cout<<'G'<<vec[0].index+1<<endl;
cout<<setiosflags(ios::fixed)<<setprecision(1)<<float(vec[0].mm)<<" "<<float(vec[0].sum)/n<<endl;
}
system( "PAUSE");
return 0;
}
最后一个Case不过，不知是哪里没考虑到。