hdu 2377

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2377
考え方:各点spfaに対して1回の最短ルートを求めて、毎回求める時すべて1つの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
",MIN,id);

78     }

79     return 0;

80 }