每个点求一次最短路，在最短路中找最长的。
用邻接表存边，尽量不要用STL，很容易超时。
#include#include #include #include using namespace std;const int MAXN = 1010;const int INF = 1 << 22;struct node{ int v, next; node() { } node( int v, int next ):v(v), next(next) { }};struct Dijkstra{ int n, m; int head[MAXN]; node edges[MAXN*22]; bool done[MAXN]; int d[MAXN]; void init( int n ) { this->n = n; this->m = 0; for ( int i = 0; i <= n; ++i ) head[i] = -1; return; } void AddEdge( int from, int to ) { edges[m].v = to; edges[m].next = head[from]; head[from] = m++; return; } void dijkstra( int s ) { int Q[MAXN*22]; for ( int i = 0; i <= n; ++i ) d[i] = INF; d[s] = 0; memset( done, false, sizeof(done) ); int front = 0; int tail = 0; Q[tail++] = s; while ( front < tail ) { int u = Q[front++]; if ( done[u] ) continue; done[u] = true; for ( int i = head[u]; i != -1; i = edges[i].next ) { int v = edges[i].v; if ( d[v] > d[u] + 1 ) { d[v] = d[u] + 1; Q[tail++] = v; } } //printf( "front=%d tail=%d\n", front, tail ); } return; }};int N, edgeN;Dijkstra slv;char name[MAXN][14];int GetNum( char *s ){ for ( int i = 1; i <= N; ++i ) { if ( !strcmp( s, name[i] ) ) return i; } return 0;}int main(){ while ( scanf("%d", &N ) == 1 && N ) { for ( int i = 1; i <= N; ++i ) scanf( "%s", name[i] ); scanf( "%d", &edgeN ); slv.init( N ); for ( int i = 0; i < edgeN; ++i ) { char a[14], b[14]; scanf( "%s%s", a, b ); int u = GetNum(a); int v = GetNum(b); slv.AddEdge( u, v ); slv.AddEdge( v, u ); } int ans = 0; for ( int i = 1; i <= N; ++i ) { slv.dijkstra( i ); for ( int j = i + 1; j <= N; ++j ) { ans = max( ans, slv.d[j] ); if ( ans >= INF ) break; } if ( ans >= INF ) break; } if ( ans >= INF ) puts("-1"); else printf( "%d\n", ans ); } return 0;}