P2951 【[USACO09OPEN]捉迷藏Hide and Seek】

典型的最短路，而且只要再加一点点操作，就能得到答案

所以可以直接套模板

具体看程序：：

 #include<cstdio>

 #include<queue>//队列专属头文件

 #include<algorithm>

 using namespace std;

 const int N=;

 int a[N];

 int n,m,l,sum,ans;

 int d1[N],t[N],head1[N],next1[N],w1[N],adj1[N],k1;

 bool f1[N];

 queue<int> q1;//比较喜欢定义全局变量

 void add(int u,int v){//加边操作，因为每条边权值为1，就不用第三个变量了

     next1[++k1]=head1[u];

     head1[u]=k1;

     w1[k1]=;//如果不是1，就把一换成变量t（自己定义）

     adj1[k1]=v;

 }

 void spfa(int s,int e){//SPFA,最短路模板

     for(int i=;i<=n;i++)

         d1[i]=<<;//赋无限大

     d1[s] =;

     q1.push(s);

     f1[s]=true ;

     while(!q1.empty()){

         int top1=q1.front() ;

         q1.pop() ;//出队

         f1[top1]=false;

         for(int j=head1[top1];j!=;j=next1[j]){

             if(d1[adj1[j]]>d1[top1]+w1[j]){//松弛操作

                 t[adj1[j]]++;

                 d1[adj1[j]]=d1[top1]+w1[j] ;

                 if(!f1[adj1[j]]){

                     q1.push(adj1[j]);

                     f1[adj1[j]]=true;

                 }

             }

         }

     }

 }

 int main(){

     //freopen("hideseek.in","r",stdin);

     //freopen("hideseek.out","w",stdout);不要在意。。。

     scanf("%d%d",&n,&m);//读入

     for(int i=;i<=m;i++){

         int x,y;

         scanf("%d%d",&x,&y);

         add(x,y);

         add(y,x);//加边操作，因为是无向图，要加两次

     }

     spfa(,n);//调用

     for(int i=;i<=n;i++){

         if(d1[i]>l){//如果出现了比现在大的点，就交换

             l=d1[i];

             ans=i;

             sum=;

         }

         else{

             if(d1[i]==l){//一样就加

                 sum++;

             }

         }

     }

     printf("%d %d %d\n",ans,l,sum);//输出

     return ;

 }

不用数组模拟队列其实蛮麻烦的，我也只是套用模板，懒得改了，比才是现场写还是要写自己有把握的

那个。。新人开博鼓励一下吧~~