HDU 4460 Friend Chains BFS 最短路

題意：給出N個人，和他們之間的朋友關系。求出最小的k，使對于任意一個人， 其他所有的人至多經過k次傳遞，成為他的朋友。

思路：很容易就能想到，這是求任意人之間最短路的最大值。但是如果直接用floyd的話，會TLE。

           我們注意到，其實距離為1，那用bfs求最短路是可行的。n次BFS即可。同時，SPFA等價于BFS。

代碼如下：

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include<queue>
#include <algorithm>
using namespace std;

char s[20],ss[20];
int b[1001000];
struct edge
{
    int v,f,nxt;
};

int n,m;
int g[1100];
int nume;
edge e[20200];

int ha(char s[])
{
    int i;
    int L=strlen(s);
    int temp=0;
    int x=1;
    for (i=0;i<L;i++)
    {
        x=x*131%1000000;
        temp=(temp+s[i]*x%1000000)%1000000;
    }
    return temp;
}

void addedge(int u,int v,int c)
{
    e[++nume].v=v;
    e[nume].f=c;
    e[nume].nxt=g[u];
    g[u]=nume;
    e[++nume].v=u;
    e[nume].f=c;
    e[nume].nxt=g[v];
    g[v]=nume;
}

int maxlen;
int maxp;
int d[1005];
bool instack[1005];
const int INF=0x3f3f3f3f;
queue<int> q;
bool vi[1005];
int total=0;
void SPFA(int u)
{
    int top,i;
    for(i=1;i<=n;i++) d[i]=INF;
    instack[u]=true;q.push(u);d[u]=0;vi[u]=true;total++;
    while(!q.empty())
    {
        top=q.front();q.pop();
        if(!vi[top]) vi[top]=true,total++;
        instack[top]=false;
        for(i=g[top];i;i=e[i].nxt)
        {
            if(d[e[i].v]>d[top]+e[i].f)
            {
                d[e[i].v]=d[top]+e[i].f;
                if(!instack[e[i].v])
                {
                    q.push(e[i].v);
                    instack[e[i].v]=true;
                }
            }

        }
    }
    for(i=1;i<=n;i++) maxlen=max(maxlen,d[i]);
}
int  main()
{
    //freopen("in","r",stdin);
    int i;
    while (~scanf("%d",&n) && n)
    {

        for (i=1;i<=n;i++)
        {
            scanf("%s",s);
            b[ha(s)]=i;
        }
        scanf("%d",&m);
        nume=0;
        memset(g,0,sizeof(g));
        for (i=1;i<=m;i++)
        {
            scanf("%s%s",s,ss);
            addedge(b[ha(s)],b[ha(ss)],1);
        }
        //memset(vis,false,sizeof(vis));
        maxlen=-1;
        for(i=1;i<=n;i++)
        {
            total=0;
            memset(vi,false,sizeof(vi));
            SPFA(i);
            if(total!=n) {maxlen=-1;break;}
        }
        printf("%d\n",maxlen);
    }
    return 0;
}