------------------------------------->[戳这里](https://cndrew.cn/blog/2019/07/25/mapsave)<-------------------------------------< font>

### Labyrinth

Description:
The northern part of the Pyramid contains a very large and complicated labyrinth. The labyrinth is divided into square blocks, each of them either filled by rock, or free. There is also a little hook on the floor in the center of every free block. The ACM have found that two of the hooks must be connected by a rope that runs through the hooks in every block on the path between the connected ones. When the rope is fastened, a secret door opens. The problem is that we do not know which hooks to connect. That means also that the neccessary length of the rope is unknown. Your task is to determine the maximum length of the rope we could need for a given labyrinth.
Input

The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers C and R (3 <= C,R <= 1000) indicating the number of columns and rows. Then exactly R lines follow, each containing C characters. These characters specify the labyrinth. Each of them is either a hash mark (#) or a period (.). Hash marks represent rocks, periods are free blocks. It is possible to walk between neighbouring blocks only, where neighbouring blocks are blocks sharing a common side. We cannot walk diagonally and we cannot step out of the labyrinth.

The labyrinth is designed in such a way that there is exactly one path between any two free blocks. Consequently, if we find the proper hooks to connect, it is easy to find the right path connecting them.
Output
Your program must print exactly one line of output for each test case. The line must contain the sentence "Maximum rope length is X." where Xis the length of the longest path between any two free blocks, measured in blocks.

Sample Input

2
3 3

7 6

# .....

###### #

Sample Output

Maximum rope length is 0.
Maximum rope length is 8.

Hint

Huge input, scanf is recommended.
If you use recursion, maybe stack overflow. and now C++/c 's stack size is larger than G++/gcc

Problem solving:

Code:

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int dis[1005][1005];
int vis[1005][1005];
char s[1005][1005];
int d[4][2]={1,0,0,1,-1,0,0,-1};
struct node{
int x,y;
};
int n,c,r,sx,sy;
int bfs(int x,int y)
{
node now,mid;
queue<node> que;
now.x=x;now.y=y;
que.push(now);
vis[x][y]=1;dis[x][y]=0;
while(!que.empty())
{
now=que.front();
que.pop();
for(int i=0;i<4;i++)
{
mid.x=now.x+d[i][0];
mid.y=now.y+d[i][1];
if(mid.x<0||mid.x>=r||mid.y<0||mid.y>=c||s[mid.x][mid.y]=='#'||vis[mid.x][mid.y])    continue;
vis[mid.x][mid.y]=1;
dis[mid.x][mid.y]=dis[now.x][now.y]+1;
que.push(mid);
}
}
}
int main()
{
scanf("%d",&n);
while(n--)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
scanf("%d %d",&c,&r);
int flag=0;
for(int i=0;i<r;i++)    scanf("%s",s[i]);
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(s[i][j]=='.')
{
sx=i,sy=j;
flag=1;
break;
}
if(flag)    break;
}
}
bfs(sx,sy);int px=0;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(dis[i][j]>px)
{
sx=i;
sy=j;
px=dis[i][j];
}
}
}
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
bfs(sx,sy);
int ans=0;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
ans=max(ans,dis[i][j]);
}
}
printf("Maximum rope length is %d.\n",ans);
}
}


### Cow Marathon

Description:
After hearing about the epidemic of obesity in the USA, Farmer John wants his cows to get more exercise, so he has committed to create a bovine marathon for his cows to run. The marathon route will include a pair of farms and a path comprised of a sequence of roads between them. Since FJ wants the cows to get as much exercise as possible he wants to find the two farms on his map that are the farthest apart from each other (distance being measured in terms of total length of road on the path between the two farms). Help him determine the distances between this farthest pair of farms.

Input

• Lines 1.....: Same input format as "Navigation Nightmare".

Output

• Line 1: An integer giving the distance between the farthest pair of farms.

Sample Input

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S

Sample Output

52

Hint

The longest marathon runs from farm 2 via roads 4, 1, 6 and 3 to farm 5 and is of length 20+3+13+9+7=52.

Problem solving:

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
int a,b,c,ans,n,m;
const int maxn = 1e5+10;
int vis[maxn],dis[maxn];
char s;
vector<pair<int,int> > v[maxn];
int bfs(int x)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
vis[x]=1;
int point=0;
queue<int> q;
q.push(x);
while(!q.empty())
{
x=q.front();
q.pop();
if(dis[x]>ans)
{
ans=dis[x];
point=x;
}
pair<int,int> mid;
for(int i=0;i<v[x].size();i++)
{
mid=v[x][i];
if(!vis[mid.first])
{
vis[mid.first]=1;
dis[mid.first]=dis[x]+mid.second;
q.push(mid.first);
}
}
}
return point;
}
int main()
{
cin>>n>>m;
while(m--)
{
cin>>a>>b>>c>>s;
v[a].push_back(make_pair(b,c));
v[b].push_back(make_pair(a,c));
}
ans=0;
int point=bfs(1);
ans=0;
bfs(point);
cout<<ans<<endl;
return 0;
}


### Roads in the North

Description:
Building and maintaining roads among communities in the far North is an expensive business. With this in mind, the roads are build such that there is only one route from a village to a village that does not pass through some other village twice.
Given is an area in the far North comprising a number of villages and roads among them such that any village can be reached by road from any other village. Your job is to find the road distance between the two most remote villages in the area.

The area has up to 10,000 villages connected by road segments. The villages are numbered from 1.
Input

Input to the problem is a sequence of lines, each containing three positive integers: the number of a village, the number of a different village, and the length of the road segment connecting the villages in kilometers. All road segments are two-way.

Output

You are to output a single integer: the road distance between the two most remote villages in the area.

Sample Input

5 1 6
1 4 5
6 3 9
2 6 8
6 1 7

Sample Output

22

Problem solving:

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
int a,b,c,ans;
const int maxn = 1e5+10;
int vis[maxn],dis[maxn];
vector<pair<int,int> > v[maxn];
int bfs(int x)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
vis[x]=1;
int point=0;
queue<int> q;
q.push(x);
while(!q.empty())
{
x=q.front();
q.pop();
if(dis[x]>ans)
{
ans=dis[x];
point=x;
}
pair<int,int> mid;
for(int i=0;i<v[x].size();i++)
{
mid=v[x][i];
if(!vis[mid.first])
{
vis[mid.first]=1;
dis[mid.first]=dis[x]+mid.second;
q.push(mid.first);
}
}
}
return point;
}
int main()
{
while(cin>>a>>b>>c)
{
v[a].push_back(make_pair(b,c));
v[b].push_back(make_pair(a,c));
}
ans=0;
int point=bfs(1);
ans=0;
bfs(point);
cout<<ans<<endl;
return 0;
}


### Computer

Description:

5
1 1
2 1
3 1
1 1

3
2
3
4
4

Problem solving:

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const long long maxn=1e5;
long long n,a,b,ans;
long long vis[maxn],dis[maxn],dis2[maxn];
vector<pair<long long,long long> > v[maxn];
long long bfs(long long x)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
ans=0;
queue<long long> q;
q.push(x);
vis[x]=1;
long long point;
while(!q.empty())
{
x=q.front();
q.pop();
if(dis[x]>ans)
{
ans=dis[x];
point=x;
}
pair<long long,long long> mid;
for(long long i=0;i<v[x].size();i++)
{
mid=v[x][i];
if(!vis[mid.first])
{
vis[mid.first]=1;
dis[mid.first]=dis[x]+mid.second;
q.push(mid.first);
}
}
}
return point;
}
int main()
{
while(cin>>n)
{
memset(v,0,sizeof(v));
for(long long i=2;i<=n;i++)
{
cin>>a>>b;
v[a].push_back(make_pair(i,b));
v[i].push_back(make_pair(a,b));
}
long long point=bfs(1);
long long next=bfs(point);
for(long long i=1;i<=n;i++)    dis2[i]=dis[i];
bfs(next);
for(long long i=1;i<=n;i++)
{
cout<<max(dis2[i],dis[i])<<endl;;
}
}
}


### Farthest Nodes in a Tree

Description:
Given a tree (a connected graph with no cycles), you have to find the farthest nodes in the tree. The edges of the tree are weighted and undirected. That means you have to find two nodes in the tree whose distance is maximum amongst all nodes.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.
Each case starts with an integer n (2 ≤ n ≤ 30000) denoting the total number of nodes in the tree. The nodes are numbered from 0 to n-1. Each of the next n-1 lines will contain three integers u v w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 10000) denoting that node u and v are connected by an edge whose weight is w. You can assume that the input will form a valid tree.

Output

For each case, print the case number and the maximum distance.

Sample Input

2
4
0 1 20
1 2 30
2 3 50
5
0 2 20
2 1 10
0 3 29
0 4 50

Sample Output

Case 1: 100
Case 2: 80

Problem solving:

Code:

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
const int maxn= 1e5+10;
using namespace std;
int dis[maxn],ans;
bool vis[maxn];
vector<pair<int,int> > v[maxn];
int bfs(int x)
{
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
queue<int> que;
que.push(x);vis[x]=1;
int point=0;
while(!que.empty())
{
int f=que.front();
que.pop();
if(dis[f]>ans)
{
ans=dis[f];
point=f;
}
pair<int,int> t;
for(int i=0;i<v[f].size();i++)
{
t=v[f][i];
if(vis[t.first]==0)
{
vis[t.first]=1;
dis[t.first]=dis[f]+t.second;
que.push(t.first);
}
}
}
return point;
}
int main()
{
int n,m,x,y,z,flag=0;
cin>>n;
while(n--)
{
memset(v,0,sizeof(v));
cin>>m;
for(int i=1;i<m;i++)
{
cin>>x>>y>>z;
v[x].push_back(make_pair(y,z));
v[y].push_back(make_pair(x,z));
}
ans=0;
int point=bfs(1);
ans=0;
bfs(point);
printf("Case %d: %d\n",++flag,ans);
}
}


### 51nod 2602 树的直径

Description:

10
1 2
2 3
3 4
3 5
3 6
3 7
3 10
6 8
6 9

4

Problem solving:

Code:

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 1e5+10;
int dis[maxn],ans,vis[maxn],n,a,b;
vector<int> v[maxn];
int bfs(int x)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
queue<int> q;
q.push(x);
vis[x]=1,dis[x]=0;
int point;
while(!q.empty())
{
x=q.front();
q.pop();
if(dis[x]>ans)
{
ans=dis[x];
point=x;
}
for(int i=0;i<v[x].size();i++)
{
if(!vis[v[x][i]])
{
vis[v[x][i]]=1;
dis[v[x][i]]=dis[x]+1;
q.push(v[x][i]);
}
}
}
return point;
}
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
ans=0;
int point=bfs(1);
ans=0;
bfs(point);
cout<<ans<<endl;
}


### 模板

------------------------------>[戳这里](https://cndrew.cn/blog/2019/07/25/mapsave)<------------------------------< font>

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
int a,b,c,ans;
const int maxn = 1e5+10;
int vis[maxn],dis[maxn];//dis数组储存的就是当前点能向一个确定的方向走的最大的距离。vis就是一个标记数组防止重复访问。
vector<pair<int,int> > v[maxn]; //用来存图，可以看成是一个二维数组,因为是有权值的，所以在vector中套用了一个pair
int bfs(int x)
{
memset(vis,0,sizeof(vis));//因为要进行多次bfs，所以每次都要清空一下数组
memset(dis,0,sizeof(dis));
vis[x]=1;//已经访问过的节点标记为1
int point=0;//用来储存当前所能走到的最远的点
queue<int> q;//用来实现bfs的队列
q.push(x);
while(!q.empty())
{
x=q.front();
q.pop();
if(dis[x]>ans)//如果当前点能走的最大的步数大于ans，ans初始为0，如果大于就更新ans和point的值
{
ans=dis[x];
point=x;
}
pair<int,int> mid;
for(int i=0;i<v[x].size();i++)//对v[x]中的每一个元素进行bfs
{
mid=v[x][i];
if(!vis[mid.first])//没访问过就继续
{
vis[mid.first]=1;//标记成已经访问过的
dis[mid.first]=dis[x]+mid.second;//这个点的能走的最大的距离多了一个dis[x]
q.push(mid.first);//放进队列以进行bfs
}
}
}
return point;//把当前走到的最远的点返回
}
int main()
{
while(cin>>a>>b>>c)
{
v[a].push_back(make_pair(b,c));//存图
v[b].push_back(make_pair(a,c));
}
ans=0;//初始化
int point=bfs(1);
ans=0;
bfs(point);//第二次以某一端点位起点的bfs
cout<<ans<<endl;
return 0;
}


### 学长标程

#### Labyrinth

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int N,M,u,v,ans;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
char MAP[1200][1200];
bool vis[1200][1200];
void dfs(int x,int y,int res){
for(int i=0;i<4;i++){
int nx=dir[i][0]+x;
int ny=dir[i][1]+y;
if(nx>=0&&nx<N&&ny>=0&&ny<M&&vis[nx][ny]==0&&MAP[nx][ny]=='.'){
vis[nx][ny]=1;
dfs(nx,ny,res+1);
}
}
if(res>=ans){
u=x;v=y;ans=res;
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&M,&N);
for(int i=0;i<N;i++){
scanf("%s",&MAP[i]);
}
memset(vis,0,sizeof(vis));
ans=0;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(MAP[i][j]=='.'){
dfs(i,j,0);
}
}
}
memset(vis,0,sizeof(vis));
dfs(u,v,0);
cout<<"Maximum rope length is "<<ans<<'.'<<endl;
}
return 0;
}


#### Cow Marathon

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int N,M,X,Y,Z,ans;
int dis[40020];
bool vis[40020];
vector<pair<int,int> >V[40020];
int bfs(int n){
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
queue<int>Q;
Q.push(n);
vis[n]=1;
ans=0;
int point=0,t;
while(!Q.empty()){
t=Q.front();
Q.pop();
if(dis[t]>ans){
ans=dis[t];
point=t;
}
for(int i=0;i<V[t].size();i++){
if(vis[V[t][i].first]==0){
vis[V[t][i].first]=1;
dis[V[t][i].first]=dis[t]+V[t][i].second;
Q.push(V[t][i].first);
}
}
}
return point;
}
int main(){
scanf("%d%d",&N,&M);
for(int i=0;i<M;i++){
scanf("%d%d%d %*c",&X,&Y,&Z);
V[X].push_back(make_pair(Y,Z));
V[Y].push_back(make_pair(X,Z));
}
bfs(bfs(1));
printf("%d\n",ans);
return 0;
}


#### Roads in the North

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int N,M,X,Y,Z,ans;
int dis[40020];
bool vis[40020];
vector<pair<int,int> >V[40020];
int bfs(int n){
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
queue<int>Q;
Q.push(n);
vis[n]=1;
ans=0;
int point=0,t;
while(!Q.empty()){
t=Q.front();
Q.pop();
if(dis[t]>ans){
ans=dis[t];
point=t;
}
for(int i=0;i<V[t].size();i++){
if(vis[V[t][i].first]==0){
vis[V[t][i].first]=1;
dis[V[t][i].first]=dis[t]+V[t][i].second;
Q.push(V[t][i].first);
}
}
}
return point;
}
int main(){
while(scanf("%d%d%d",&X,&Y,&Z)!=EOF){
V[X].push_back(make_pair(Y,Z));
V[Y].push_back(make_pair(X,Z));
}
bfs(bfs(1));
printf("%d\n",ans);
return 0;
}


#### Computer

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int N,M,X,Y,Z,ans;
int dis[40020];
int diss[40020];
bool vis[40020];
vector<pair<int,int> >V[40020];
int bfs(int n){
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
queue<int>Q;
Q.push(n);
vis[n]=1;
ans=0;
int point,t;
while(!Q.empty()){
t=Q.front();
Q.pop();
if(dis[t]>ans){
ans=dis[t];
point=t;
}
for(int i=0;i<V[t].size();i++){
if(vis[V[t][i].first]==0){
vis[V[t][i].first]=1;
dis[V[t][i].first]=dis[t]+V[t][i].second;
Q.push(V[t][i].first);
}
}
}
return point;
}
int main(){
while(scanf("%d",&N)!=EOF){
for(int i=0;i<=N;i++)V[i].clear();
for(int i=1;i<N;i++){
scanf("%d%d",&X,&Z);
V[i+1].push_back(make_pair(X,Z));
V[X].push_back(make_pair(i+1,Z));
}
int point=bfs(bfs(1));
for(int i=1;i<=N;i++){
diss[i]=dis[i];
}
bfs(point);
for(int i=1;i<=N;i++){
printf("%d\n",max(dis[i],diss[i]));
}
}
return 0;
}


#### Farthest Nodes in a Tree

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int N,M,X,Y,Z,ans;
int dis[40020];
bool vis[40020];
vector<pair<int,int> >V[40020];
int bfs(int n){
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
queue<int>Q;
Q.push(n);
vis[n]=1;
ans=0;
int point,t;
while(!Q.empty()){
t=Q.front();
Q.pop();
if(dis[t]>ans){
ans=dis[t];
point=t;
}
for(int i=0;i<V[t].size();i++){
if(vis[V[t][i].first]==0){
vis[V[t][i].first]=1;
dis[V[t][i].first]=dis[t]+V[t][i].second;
Q.push(V[t][i].first);
}
}
}
return point;
}
int main(){
int T,Case=1;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
for(int i=0;i<N;i++)V[i].clear();
for(int i=1;i<N;i++){
scanf("%d%d%d",&X,&Y,&Z);
V[X].push_back(make_pair(Y,Z));
V[Y].push_back(make_pair(X,Z));
}
bfs(bfs(0));
printf("Case %d: %d\n",Case++,ans);
}
return 0;
}


#### 树的直径

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int N,M,X,Y,Z,ans;
int dis[100020];
bool vis[100020];
vector<pair<int,int> >V[100020];
int bfs(int n){
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
queue<int>Q;
Q.push(n);
vis[n]=1;
ans=0;
int point,t;
while(!Q.empty()){
t=Q.front();
Q.pop();
if(dis[t]>ans){
ans=dis[t];
point=t;
}
for(int i=0;i<V[t].size();i++){
if(vis[V[t][i].first]==0){
vis[V[t][i].first]=1;
dis[V[t][i].first]=dis[t]+V[t][i].second;
Q.push(V[t][i].first);
}
}
}
return point;
}
int main(){
scanf("%d",&N);
for(int i=1;i<N;i++){
scanf("%d%d",&X,&Y);
V[X].push_back(make_pair(Y,1));
V[Y].push_back(make_pair(X,1));
}
bfs(bfs(1));
printf("%d\n",ans);
return 0;
}