分糖果-526互联

9692: 分糖果

分析：本题核心是求从某点出发到所有其它点的最短路径的最大值。相邻节点间的传送时间都是1秒，也就是图中所有边长都是1.所有可以用bfs解决。

图的存储：

我们选用邻接表，用vector数组来实现。

vector<int>G[maxN];

G是一维数组，数组元素的数据类型是vector。

G[i] 中存放i为起点的所有边的终点组成的向量。

给向量添加值的语法是：“向量名.push_back(值)”，

譬如：

　　添加一条边1-->2 可以写成　G[1].push_back(2);

　　　　添加一条边 2-->1 可以写成　G[2].push_back(1);

　　由于这是个无向图，所以读入的两个点u,v ，都可以是起点或终点，

所以要建方向相反的两条边：

G[u].push_back(v);

G[v].push_back(u);

样例图在G中的数据为

const int maxN=1010;
vector<int>G[maxN];   
cin>>n>>p；
 for(int i=1;i<=p;i++)
     {
         int u,v; cin>>u>>v;     
         G[u].push_back(v);
         G[v].push_back(u);
     }

若想遍历h为起点的边，只要遍历向量G[v]就可以了。

1  for(int i=0;i<G[h].size();i++){
2             int v=G[h][i];
3             cout<<h<<"  "<<v<<endl;
4        }

完整代码：

 1  
 2 # include <bits/stdc++.h>
 3 using namespace std;
 4 const int maxN=1010;
 5 vector<int>G[maxN];
 6   
 7 int d[maxN];//d[i]表示搜索起点到i的距离。 
 8 int n,p,c,m;
 9  
10 bool flag,visited[maxN];
11   
12 void bfs(int s){
13     queue<int> Q;
14     Q.push(s);d[s]=0;
15     while (!Q.empty()){
16         int h=Q.front();Q.pop();
17         visited[h]=true;
18          
19         for(int i=0;i<G[h].size();i++){
20             int v=G[h][i];
21             if(!visited[v]){
22                  visited[v]=true; 
23                  d[v]=d[h]+1;
24                  Q.push(v);
25             }
26         }
27     }
28 }
29   
30 int main(){
31      cin>>n>>p>>c;
32      cin>>m;
33  
34      for(int i=1;i<=p;i++)
35      {
36          int u,v; cin>>u>>v;     
37          G[u].push_back(v);
38          G[v].push_back(u);
39      }
40           
41      bfs(c);
42      int maxL=d[1];
43      for(int i=2;i<=n;i++) maxL=max(maxL,d[i]); 
44      cout<<maxL+1+m<<endl;
45              
46     return 0;
47 }