hdu 4460 求所有任意两点间的最短路

Friend ChainsTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 575    Accepted Submission(s): 258


Problem DescriptionInputOutputSample InputSample OutputSource//============================================================================// Name : HDU4460.cpp// Author : // Version :// Copyright : Your copyright notice// Description : Hello World in C++, Ansi-style//============================================================================#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <map>#include <math.h>#include <queue>#include <vector>#include<string>using namespace std;const int MAXN=1010;const int INF=0x3f3f3f3f;int dis[MAXN][MAXN];bool used[MAXN];vector<int>vec[MAXN];queue<int>que;void bfs(int i){ memset(used,false,sizeof(used)); dis[i][i]=0; used[i]=true; que.push(i); while(!que.empty()) { int t=que.front(); que.pop(); int m=vec[t].size(); for(int j=0;j<m;j++) { int v=vec[t][j]; if(used[v])continue;//从某点到某点如果有多条路 根据que的性质可以知道最短的路径会被先标记 所以就不用再走了if(dis[i][v]>dis[i][t]+1)//由于权值都是1 这句话也可以不加 dis[i][v]=dis[i][t]+1; que.push(v); used[v]=true; } }}map<string,int>mp;int main() { string str; string str2; int n,m,i,j; while(scanf("%d",&n)==1 && n) { mp.clear(); for(i=0;i<n;i++) { cin>>str; mp[str]=i; } for(i=0;i<n;i++) { dis[i][i]=0; for(j=i+1;j<n;j++) dis[i][j]=dis[j][i]=INF; } scanf("%d",&m); for(i=0;i<n;i++)vec[i].clear(); while(m--) { cin>>str>>str2; int t1=mp[str]; int t2=mp[str2]; vec[t1].push_back(t2); vec[t2].push_back(t1); } for(i=0;i<n;i++)bfs(i); int ans=0; for(i=0;i<n;i++) for(j=i+1;j<n;j++) ans=ans>dis[i][j]?ans:dis[i][j]; if(ans==INF)ans=-1; printf("%d\n",ans); } return 0;}