首页 > 代码库 > hdu 4460
hdu 4460
break point 在 边数很少,o(n*m)暴力出奇迹~~~
+ View Code?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | #include<iostream> #include<map> #include<string> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn = 1005, maxm = 22222, inf=2000; int n, m, cnt; int h[maxn], d[maxn][maxn]; map<string, int > mp; struct edge{ int v, nxt; }e[maxm]; void add( int u, int v){ e[cnt] = (edge){v, h[u]}; h[u]=cnt++; e[cnt]=(edge){u, h[v]}; h[v]=cnt++; d[u][v]=d[v][u]=1; } int vis[maxn]; void dijkstra( const int s){ queue< int > q; memset (vis, 0, sizeof (vis)); q.push(s); vis[s]=1; while (!q.empty()){ int u = q.front(); q.pop(); for ( int i=h[u]; i!=-1; i=e[i].nxt){ int v = e[i].v; if (vis[v]) continue ; d[v][s]=d[s][v]=min(d[s][v], d[s][u]+1); q.push(v), vis[v]=1; } } } int main(){ while ( scanf ( " %d" , &n)==1 && n){ int i, j; string s1, s2; char n1[12], n2[12]; mp.clear(); for (i=0; i<n; i++){ scanf ( " %s" , n1); mp[s1=n1]=i; } cnt=0; memset (h, -1, sizeof (h)); for (i=0; i<n; i++) for (j=0; j<n; j++) d[i][j]=i==j?0:inf; scanf ( " %d" , &m); while (m--){ scanf ( " %s %s" , n1, n2); add(mp[s1=n1], mp[s2=n2]); } for (i=0; i<n; i++) dijkstra(i); int ans = 0; for (i=0; i<n; i++) for (j=i+1; j<n; j++){ ans=max(ans, d[i][j]); } printf ( "%d\n" , ans==inf?-1:ans); } return 0; } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。