题目：//https://www.hackerearth.com/zh/practice/algorithms/graphs/breadth-first-search/practice-problems/algorithm/agitated-chandan/description/
Chandan is a horrendous murderer and he wants to kill Arjit just because he's lazy. Chandan is following the trail of Arjit's shoes. The trail is in the form of a k-ary tree. Arjit is lazy, sure, but he's smart. Initially, Arjit and Chandan are standing together, but Arjit magically moves away from Chandan as far as he can go.
Chandan doesn't know the way out, but he knows that Arjit has managed to travel the maximum distance he can. Help Chandan find out the maximum distance he would have to travel to find Arjit. And also tell him how much will he have to pay to travel so far. The travel rates are:
- If maximum distance is <100, cost = 0.
- If maximum distance is > 100, cost = 100.
- If maximum distance is > 1000, cost = 1000.
- If maximum distance is > 10000, cost = 10000.
Input format:
First line contains the total number of test cases. Then, the next line contains the number of nodes. The the next n-1 lines contain three integers - the first two denote an edge between a and b, the third integer denotes the weight of that edge.
Output format:
You've to print the money Chandan will pay and the maximum distance he will have to travel.
Constraints:
1 <= Test Cases <= 10
2 <= n <= 100000
1 <= a, b <= n
1 <= weight <= 100
代码：dfs
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
ll dist[100009];
ll vis[100009];
vector< pair<ll,ll> >adj[100009];
void dfs(ll x)
{
ll v,w;
vis[x]=1;
for(int i=0;i<adj[x].size();i++)
{
v=adj[x][i].first;
w=adj[x][i].second;
if(!vis[v])
{
dist[v]=dist[x]+w;
dfs(v);
}
}
}
int main()
{
ll T,t,n,a,b,c,i,maxi;
cin>>T;
for(int t=1;t<=T;t++)
{
cin>>n;
for(i=0;i<=n;i++)
adj[i].clear();
for(int i=1;i<n;i++)
{
cin>>a>>b>>c;
adj[a].push_back(make_pair(b,c));
adj[b].push_back(make_pair(a,c));
}
memset(vis,0,sizeof(vis));
memset(dist,0,sizeof(dist));
dfs(1);
maxi=0;
a=0;
for(int i=1;i<=n;i++)
{
if(dist[i]>maxi)
{
maxi=dist[i];
a=i;
}
}
memset(vis,0,sizeof(vis));
memset(dist,0,sizeof(dist));
dfs(a);
maxi=0;
a=0;
for(int i=1;i<=n;i++)
{
if(dist[i]>maxi)
{
maxi=dist[i];
a=i;
}
}
if(maxi>10000)
a=10000;
else if(maxi>1000)
a=1000;
else if(maxi>100)
a=100;
else
a=0;
printf("%lld %lld\n",a,maxi);
}
return 0;
}#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int dist[100001];
int vis[100001];
int n, tme;
struct node {
int i,d;
};
typedef struct node node;
vector<node> adj[100001];
void bfs(int start){
queue<int>q;
q.push(start);
vis[start]=1;
while(!q.empty())
{
int p=q.front();
q.pop();
for(int i=0;i<(int)adj[p].size();i++)
{
if(vis[adj[p][i].i]==0){
vis[adj[p][i].i]=1;
dist[adj[p][i].i]=dist[p]+adj[p][i].d;
q.push(adj[p][i].i);
}
}
}
}
int main()
{
int u,v,w;
node temp;
int test;
cin>>test;
while(test--)
{
cin>>n;
for(int i=1;i<=n;i++) {
adj[i].clear();
}
for(int i=1;i<n;i++)
{
cin>>u>>v>>w;
temp.i=v;
temp.d=w;
adj[u].push_back(temp);
temp.i=u;
adj[v].push_back(temp);
}
memset(vis,0,sizeof(vis));
memset(dist,0,sizeof(dist));
bfs(1);
int maxi=0;
int a=0;
for(int i=1;i<=n;i++)
{
if(dist[i]>maxi)
{
maxi=dist[i];
a=i;
}
}
memset(vis,0,sizeof(vis));
memset(dist,0,sizeof(dist));
bfs(a);
maxi=0;
a=0;
for(int i=1;i<=n;i++)
{
if(dist[i]>maxi)
{
maxi=dist[i];
a=i;
}
}
if(maxi>10000)
a=10000;
else if(maxi>1000)
a=1000;
else if(maxi>100)
a=100;
else
a=0;
printf("%d %d\n",a,maxi);
}
return 0;
}