PAT L3-005. 垃圾箱分布

最短路。

枚举垃圾箱放哪里，然后算最短路。

#include<map>

#include<set>

#include<ctime>

#include<cmath>

#include<queue>

#include<string>

#include<stack>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

int n,m,k,ds;

char u[];

vector<int>g[];

int v[][];

int dis[], f[];

int fail=;

int ansLen=-,avg=-,id=-;

int get()

{

    int sum=;

    if(u[]!='G')

    {

        for(int i=;u[i];i++) sum=sum*+u[i]-'';

    }

    else

    {

        for(int i=;u[i];i++) sum=sum*+u[i]-'';

        sum = sum + n;

    }

    return sum;

}

void spfa(int x)

{

    for(int i=;i<=n+m;i++) dis[i] = 0x7FFFFFFF;

    queue<int>Q; memset(f,,sizeof f);

    dis[x]=; f[x]=; Q.push(x);

    while(!Q.empty())

    {

        int h= Q.front(); Q.pop(); f[h]=;

        for(int i=;i<g[h].size();i++)

        {

            int to = g[h][i];

            if(dis[h]+v[h][to]<dis[to])

            {

                dis[to] = dis[h]+v[h][to];

                if(f[to]==)

                {

                    f[to]=;

                    Q.push(to);

                }

            }

        }

    }

    for(int i=;i<=n;i++) if(dis[i]>ds) return ;

    fail=;

    int mi=0x7FFFFFFF,sum=;

    for(int i=;i<=n;i++) sum=sum+dis[i],mi = min(mi,dis[i]);

    if(id==-)

    {

        id = x;

        ansLen = mi;

        avg = sum;

    }

    else

    {

        if(mi>ansLen)

        {

            id = x;

            ansLen = mi;

            avg = sum;

        }

        else if(mi==ansLen)

        {

            if(sum<avg)

            {

                id = x;

                ansLen = mi;

                avg = sum;

            }

        }

    }

}

int main()

{

    scanf("%d%d%d%d",&n,&m,&k,&ds);

    for(int i=;i<=k;i++)

    {

        int c;

        scanf("%s",u); int A = get();

        scanf("%s",u); int B = get();

        scanf("%d",&c);

        v[A][B]=v[B][A]=c;

        g[A].push_back(B); g[B].push_back(A);

    }

    for(int i=n+;i<=n+m;i++)

    {

        spfa(i);

    }

    if(fail) printf("No Solution\n");

    else

    {

        printf("G%d\n",id-n);

        printf("%.1f %.1f\n",1.0*ansLen,1.0*avg/n);

    }

    return ;

}