1072 Gas Station

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

由于m很小（m<=10），所以可以枚举每一个加油站位置，每一个都是一个单源最短路径问题 ，使用Dijkstra记录距离，结束后遍历dis数组，只要有一个距离超过ds说明该答案不可行，最终对答案数组进行自定义排序，在该答案可行（flag==0）的前提下输出第一个即可，否则输出No Solution。

具体见代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
//n小于等于1000，所以将加油站的编号+1000作为新编号，放入一张图中
int dis[25][2020];//每个位置的加油站到每个房子的距离
bool vis[2020];
int n, m, k, ds, d, t1, t2;
string x, y;
int ans;//答案编号
 
struct edge {
	int next, dis;
};
priority_queueint, int>, vectorint, int>>, greaterint, int>>>q;
vectorg[2020];
 
 
struct Ind {
	double minn, avg; //最小距离，平均距离
	int indexx;//编号
	bool flag;//答案是否可行, 0可行
} a[20];
 
bool cmp(Ind i1, Ind i2) {
	return i1.minn == i2.minn ? (i1.avg == i2.avg ? i1.indexx < i2.indexx : i1.avg < i2.avg) : i1.minn > i2.minn;
}
 
int main() {
	cin >> n >> m >> k >> ds;
	for (int i = 0; i < k; i++) {
		cin >> x >> y >> d;
		t1 = 0, t2 = 0;
		if (x[0] == 'G') {
			for (int j = 1; j < x.size(); j++) {
				t1 = t1 * 10 + x[j] - '0';
			}
			t1 += 1000;
		} else {
			t1 = atoi(x.c_str());
		}
		if (y[0] == 'G') {
			for (int j = 1; j < y.size(); j++) {
				t2 = t2 * 10 + y[j] - '0';
			}
			t2 += 1000;
		} else {
			t2 = atoi(y.c_str());
		}
		edge e;
		e.next = t2;
		e.dis = d;
		g[t1].push_back(e);
		e.next = t1;
		g[t2].push_back(e);
	}
	for (int i = 1; i <= m; i++) {
		priority_queueint, int>, vectorint, int>>, greaterint, int>>>empty;
		swap(empty, q);
		memset(dis[i], 127, sizeof(dis[i]));
		memset(vis, 0, sizeof(vis));
		dis[i][i + 1000] = 0;
		q.push(make_pair(0, i + 1000));
		while (!q.empty()) {
			int u = q.top().second;
			q.pop();
			if (vis[u]) {
				continue;
			}
			vis[u] = 1;
			for (int j = 0; j < g[u].size(); j++) {
				int v = g[u][j].next;
				if (dis[i][v] > dis[i][u] + g[u][j].dis) {
					dis[i][v] = dis[i][u] + g[u][j].dis;
					q.push(make_pair(dis[i][v], v));
				}
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		a[i].indexx = i;
		a[i].flag = 0;
		a[i].avg = 0;
		a[i].minn = (1 << 30);
		for (int j = 1; j <= n; j++) {
			if (dis[i][j] > ds) {
				a[i].flag = 1;
				break;
			}
			a[i].avg += dis[i][j] * 1.0;
			if (dis[i][j] < a[i].minn) {
				a[i].minn = dis[i][j] * 1.0;
			}
		}
		a[i].avg /= (1.0 * n);
		if (a[i].avg - (((int)(a[i].avg * 10)) * 1.0 / 10.0 + 0.05) >= 0.0) {
			a[i].avg = ((int)(a[i].avg * 10)) * 1.0 / 10.0 + 0.1;
		}
	}
	sort(a + 1, a + 1 + m, cmp);
	for (int i = 1; i <= m; i++) {
		if (!a[i].flag) {
			cout << 'G' << a[i].indexx << endl;
			cout << setprecision(1) << fixed << a[i].minn << ' ' << setprecision(1) << fixed << a[i].avg;
			return 0;
		}
	}
	cout << "No Solution";
	return 0;
}