HDU 4460 Friend Chains 【bfs】【spfa】

点击打开链接

题意，求两两朋友之间的最短路中的最大值。

我一直理解错题意，能写过才奇怪了！！！！，

题解：用bfs  把每个能走的朋友都走一遍，然后记录最远的距离。

    最后求最大值。

#include<iostream>
#include<string>
#include<stdio.h>
#include<string.h>
#include<map>
#include<queue>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=1111;
const int inf=0xffffff;
queue<int>que;
int dis[maxn][maxn];
int v[maxn];
char s[20],s1[20],s2[20];
int n,q;
map<string ,int>m;
vector<int>vec[maxn];
void bfs(int a){
    memset(v,0,sizeof(v));
    v[a]=1;
    dis[a][a]=0;
    que.push(a);
    while(!que.empty()){
        int t=que.front();
        que.pop();
        for(int k=0;k<vec[t].size();++k){
            int f=vec[t][k];
            if(!v[f]){
                v[f]=1;
                dis[a][f]=dis[a][t]+1;
                que.push(f);
            }
        }
    }
}
int main(){

    while(scanf("%d",&n)&&n){
        m.clear();
        for(int i=1;i<=n;++i) vec[i].clear();
        for(int i=1;i<=n;++i) scanf("%s",s),m[s]=i;
        scanf("%d",&q);
        while(q--){
            scanf("%s %s",s1,s2);
            vec[m[s2]].push_back(m[s1]);
            vec[m[s1]].push_back(m[s2]);
        }
        for(int i=1;i<=n;++i){
            dis[i][i]=0;
            for(int j=i+1;j<=n;++j){
                dis[i][j]=dis[j][i]=inf;
            }
        }
        for(int i=1;i<=n;++i) bfs(i);
        int ans=0;
        for(int i=1;i<=n;++i){
            for(int j=i+1;j<=n;++j)
                ans=max(ans,dis[i][j]);
        }
        if(ans==inf)printf("-1\n");
        else printf("%d\n",ans);
    }

    return 0;
}
           

我又用spfa 做了一遍。 还是bfs直接找快一点。

#include<iostream>
#include<string>
#include<stdio.h>
#include<string.h>
#include<map>
#include<queue>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=1111;
const int maxm=10111;
const int inf=0xffffff;
queue<int>que;
int dis[maxn];
int head[maxn];
int v[maxm*2];
char s[20],s1[20],s2[20];
int n,q,cnt,ans;
map<string ,int>m;
struct node{
    int to,w,nxt;
}edge[maxm*2];

int addedge(int x,int y){
    cnt++;
    edge[cnt].to=y;
    edge[cnt].w=1;
    edge[cnt].nxt=head[x];
    head[x]=cnt;
}
int spfa(int s){
    memset(v,0,sizeof(v));
    for(int i=1;i<=n;++i) dis[i]=inf;
    queue<int>que;
    dis[s]=0;
    que.push(s);
    while(!que.empty()){
        int u=que.front();
        que.pop();
        v[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].nxt){
            int e=edge[i].to;
            if(dis[e]>dis[u]+edge[i].w){
                dis[e]=dis[u]+edge[i].w;
                if(!v[e]) {
                    v[e]=1;
                    que.push(e);
                }
            }

        }
    }
    for(int i=1;i<=n;++i)
        ans=max(ans,dis[i]);
    return ans;
}
int main(){

    while(scanf("%d",&n)&&n){
        m.clear();cnt=0;ans=0;
        for(int i=1;i<=n;++i) scanf("%s",s),m[s]=i;
        scanf("%d",&q);
        memset(head,-1,sizeof(head));
        while(q--){
            scanf("%s %s",s1,s2);
            addedge(m[s1],m[s2]);
            addedge(m[s2],m[s1]);
        }
        for(int i=1;i<=n;++i) {
                if(spfa(i)==inf) break;
        }
        if(ans==inf)printf("-1\n");
        else printf("%d\n",ans);
    }

    return 0;
}