垃圾箱分布 PTA 就剩最后一个点过不了，本来想试试spfa的.....

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

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

输入格式： 输入第一行给出4个正整数：N（≤10^ 3 ）是居民点的个数；M（≤10）是垃圾箱候选地点的个数；K（≤10^ 4 ）是居民点和垃圾箱候选地点之间的道路的条数；DS 是居民点与垃圾箱之间不能超过的最大距离。所有的居民点从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
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1015;
int n,m,k,d;
int s,e,len;
set 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 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 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::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; 
            //coutedis<<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()'9')
    {
        if(cin.get()=='G')flag=1;
    }
    scanf("%d",&s);
    if(flag)s+=1000;
    flag=0;
    while(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::iterator it;
    for(it=ss.begin();it!=ss.end();it++)
    {
        dijkstra(*it);
        //cout<<endl;
    }

    if(ans)
    {
        printf("G%d
",pans-1000);
        printf("%d.0 %.1f
",mindis,averdis+0.05);
    }
    else
    {
        cout<<"No Solution"<<endl;
    }
    return 0;
}