7-9 垃圾箱分布 （30 分)
大家倒垃圾的时候，都希望垃圾箱距离自己比较近，但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，同时还要保证每个居民点都在距离它一个不太远的范围内。

现给定一个居民区的地图，以及若干垃圾箱的候选地点，请你推荐最合适的地点。如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。

输入格式：
输入第一行给出4个正整数：N（≤10^ ​3​​ ）是居民点的个数；M（≤10）是垃圾箱候选地点的个数；K（≤10^ ​4​​ ）是居民点和垃圾箱候选地点之间的道路的条数；D​S​​ 是居民点与垃圾箱之间不能超过的最大距离。所有的居民点从1到N编号，所有的垃圾箱候选地点从G1到GM编号。

随后K行，每行按下列格式描述一条道路：

P1 P2 Dist
其中P1和P2是道路两端点的编号，端点可以是居民点，也可以是垃圾箱候选点。Dist是道路的长度，是一个正整数。

输出格式：
首先在第一行输出最佳候选地点的编号。然后在第二行输出该地点到所有居民点的最小距离和平均距离。数字间以空格分隔，保留小数点后1位。如果解不存在，则输出No Solution。

输入样例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
输出样例1：
G1
2.0 3.3
输入样例2：
2 1 2 10
1 G1 9
2 G1 20
输出样例2：
No Solution

dijkstra找最短路径
在所有符合人们的居住地点距离垃圾箱都不超过sd时
按照人们据垃圾箱最短的距离的最大的那个输出
如果最短距离相等
那么按平均值低的输出
如果平均值相同，
那么按序号低的输出

下面的代码有一个点过不了：

#include<bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;

const int maxn=1015;

int n,m,k,d;

int s,e,len;

set<int> ss;

class D
{
	public:
		int dis;
		int e;
		D()
		{
			dis=inf;
			e=0;
		}
};

bool operator < (const D a,const D b)
{
	return a.dis>b.dis;
}

vector<D> g1[maxn];

D dis[maxn];

bool vis[maxn];

int ans=0;

int mindis=0;
double averdis=inf;
int pans=0;

void outdis()
{
	for(int i=1;i<=n;i++)
	{
		cout<<dis[i].e<<" "<<dis[i].dis<<endl;
	}
}

void dijkstra(int start)
{
	//cout<<"start is "<<start<<endl;
	memset(vis,0,sizeof(vis));
	for(int i=1;i!=maxn;i++)
	{
		dis[i].dis=inf;
		dis[i].e=i;
	}
	
	dis[start].dis=0;
	priority_queue<D> q;
	D t;
	t.e=start;
	t.dis=0;
	q.push(t);
	while(q.size())
	{
		D t2 = q.top();
		q.pop();
		if(vis[t2.e])continue;
		//cout<<"q top is "<<t2.e<<" "<<t2.dis<<endl;
		vis[t2.e]=1;
		vector<D>::iterator it;
		//cout<<"it "<<t2.e<<" size is "<<g1[t2.e].size()<<endl;
		for(it = g1[t2.e].begin();it!=g1[t2.e].end();it++)
		{
			int td = dis[t2.e].dis+it->dis;	
			//cout<<"it is "<<it->e<<" "<<it->dis<<endl;
			if(dis[it->e].dis>td)
			{
				dis[it->e].dis=td;
				D t3;
				t3.dis=td;
				t3.e=it->e;
				q.push(t3);
			}
		}
		//outdis();
	}
	
	int sum=0;
	int mind=inf;
	double averd;
	for(int i=1;i<=n;i++)
	{
		mind=min(mind,dis[i].dis);
		sum+=dis[i].dis;
		if(dis[i].dis>d)sum=inf;
		if(sum>=inf)break;
	}
	averd=sum*1.0/n;
	
	//cout<<sum<<" "<<mind<<" "<<averd<<endl;
	
	if(sum<inf)
	{
		ans=1;
		if(mind==mindis)
		{
			if(fabs(averd-averdis)>0.00001)
			{
				if(averd<averdis)
				{
					pans=start;	
					mindis=mind;
					averdis=averd;
				}	
			}
		}
		else
		if(mind>mindis)
		{
			pans=start;	
			mindis=mind;
			averdis=averd;
		}
	}
}

void read()
{
	bool flag=0;
	while(cin.peek()<'0'||cin.peek()>'9')
	{
		if(cin.get()=='G')flag=1;
	}
	scanf("%d",&s);
	if(flag)s+=1000;
	flag=0;
	while(cin.peek()<'0'||cin.peek()>'9')
	{
		if(cin.get()=='G')flag=1;
	}
	scanf("%d %d",&e,&len);
	if(flag)e+=1000;
}

int main()
{
	
	scanf("%d %d %d %d",&n,&m,&k,&d);
	for(int i=0;i!=k;i++)
	{
		read();
		D t;
		t.e=e;
		t.dis=len;
		//cout<<s<<" "<<t.e<<" "<<t.dis<<endl;
		g1[s].push_back(t);
		t.e=s;
		g1[e].push_back(t);
		if(e>1000)
		{
			ss.insert(e);
		}
	}

	set<int>::iterator it;
	for(it=ss.begin();it!=ss.end();it++)
	{
		dijkstra(*it);
		//cout<<endl;
	}
	
	if(ans)
	{
		printf("G%d\n",pans-1000);
		printf("%d.0 %.1f\n",mindis,averdis+0.05);
	}
	else
	{
		cout<<"No Solution"<<endl;
	}
	return 0;
}