hdu 2377

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2377

思路：对每个点spfa求一次最短路，每次求的时候都要用一个MAX_dist[]来保存当前点到各点的最短路径的最大值，然后这个数组中的min值就是star value了。。。

View Code

 1 #include<iostream>
 2 #include<queue>
 3 #include<vector>
 4 const int MAXN=10000+10;
 5 const int inf=1<<30;
 6 using namespace std;
 7 struct Node{
 8     int v,w;
 9 };
10 vector<Node>mp[MAXN];
11 int dist[MAXN];
12 bool visited[MAXN];
13 int MAX_dist[MAXN];
14 int n,m;
15 
16 void SPFA(int u){
17     for(int i=1;i<MAXN;i++)dist[i]=inf;
18     dist[u]=1;
19     if(MAX_dist[u]==-1)MAX_dist[u]=1;
20     memset(visited,false,sizeof(visited));
21     queue<int>Q;
22     Q.push(u);
23     while(!Q.empty()){
24         int u=Q.front();
25         Q.pop();
26         visited[u]=false;
27         for(int i=0;i<mp[u].size();i++){
28             int v=mp[u][i].v;
29             int w=mp[u][i].w;
30             if(dist[u]+w<dist[v]){
31                 dist[v]=dist[u]+w;
32                 if(dist[v]>MAX_dist[v])MAX_dist[v]=dist[v];
33                 if(!visited[v]){
34                     Q.push(v);
35                     visited[v]=true;
36                 }
37             }
38         }
39     }
40 }
41     
42 
43 int main(){
44     int _case;
45     scanf("%d",&_case);
46     while(_case--){
47         scanf("%d%d",&n,&m);
48         for(int i=1;i<MAXN;i++)mp[i].clear();
49         memset(MAX_dist,-1,sizeof(MAX_dist));
50         for(int i=1;i<=n;i++){
51             int u,v,k;
52             scanf("%d%d",&u,&k);
53             for(int j=1;j<=k;j++){
54                 scanf("%d",&v);
55                 Node p1,p2;
56                 p1.v=u,p2.v=v;
57                 p1.w=p2.w=1;
58                 mp[u].push_back(p2);
59                 mp[v].push_back(p1);
60             }
61         }
62         while(m--){
63             int u,k;
64             scanf("%d",&k);
65             for(int i=1;i<=k;i++){
66                 scanf("%d",&u);
67                 SPFA(u);
68             }
69         }
70         int MIN=inf,id=1;
71         for(int i=1;i<MAXN;i++){
72             if(MAX_dist[i]!=-1&&MAX_dist[i]<MIN){
73                 MIN=MAX_dist[i];
74                 id=i;
75             }
76         }
77         printf("%d %d\n",MIN,id);
78     }
79     return 0;
80 }