Using BFS:
/* Bismillahir Rahmanir Rahim
Solution-Using BFS
Find the farthest two nodes and calculate all nodes distance
from both farthest nodes and take the maximum for each node
*/
#include<bits/stdc++.h>
#define fi(n, m) for(int i=n; i<=m; i++)
#define fii(i, n, m) for(int i=n; i<=m; i++)
using namespace std;
vector<int>vt[30001], cost[30001];
int n, dis[30001], dis1[30001], a1, a2, p, cnt=0;
void bfs(int st){
fi(0, n) dis[i]=-1;
int mx=-1;
queue<int>q;
q.push(st);
dis[st]=0;
while(!q.empty()){
int u=q.front();
q.pop();
if(mx<dis[u]){
mx=dis[u];
p=u;
}
for(int j=0; j<vt[u].size(); j++){
int v=vt[u][j];
if(dis[v]==-1){
dis[v]=dis[u]+cost[u][j];
q.push(v);
}
}
}
}
void bfs1(int st){
fi(0, n) dis1[i]=-1;
queue<int>q;
q.push(st);
dis1[st]=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(int j=0; j<vt[u].size(); j++){
int v=vt[u][j];
if(dis1[v]==-1){
dis1[v]=dis1[u]+cost[u][j];
q.push(v);
}
}
}
}
int main()
{
int t, cs=1, u, v, w;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
fi(1, n-1){
scanf("%d%d%d", &u, &v, &w);
vt[u].push_back(v);
vt[v].push_back(u);
cost[u].push_back(w);
cost[v].push_back(w);
}
bfs(0); // find an ending point of farthest path
a1=p;
// find another ending point a2 and distance from a1 (dis[])
bfs(a1);
a2=p;
bfs1(a2); //calculating distance from a2(dis1[])
printf("Case %d:\n", cs++);
fi(0, n-1){
printf("%d\n", max(dis[i], dis1[i]));
vt[i].clear(); cost[i].clear();
}
}
return 0;
}
|
Using DFS:
/* Bismillahir Rahmanir Rahim
Solution-Using DFS
Find the farthest two nodes and calculate all nodes distance
from both farthest nodes and take the maximum for each node
*/
#include<bits/stdc++.h>
#define fi(n, m) for(int i=n; i<=m; i++)
#define fii(i, n, m) for(int i=n; i<=m; i++)
using namespace std;
vector<int>vt[30009], cost[30009];
int dis[30009], dis1[30009], vis[30009], n, p, mx;
void dfs(int at){
if(vis[at]) return ;
else{
vis[at]=1;
if(mx<dis[at]){
mx=dis[at];
p=at;
}
for(int j=0; j<vt[at].size(); j++){
int v=vt[at][j];
if(dis[v]==-1){
dis[v]=dis[at]+cost[at][j];
dfs(v);
}
}
}
}
void dfs1(int at){
if(vis[at]) return ;
else{
vis[at]=1;
for(int j=0; j<vt[at].size(); j++){
int v=vt[at][j];
if(dis1[v]==-1){
dis1[v]=dis1[at]+cost[at][j];
dfs1(v);
}
}
}
}
int main(){
int t, cs=1, u, v, w, a1, a2;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
fi(1, n-1){
scanf("%d%d%d", &u, &v, &w);
vt[u].push_back(v);
vt[v].push_back(u);
cost[u].push_back(w);
cost[v].push_back(w);
}
fi(0, n+1){vis[i]=0; dis[i]=-1;}
mx=0, dis[0]=0;
dfs(0); // find an ending point of farthest path
a1=p, mx=0;
fi(0, n+1){vis[i]=0; dis[i]=-1;}
dis[a1]=0;
// find another ending point a2 and distance from a1(dis[])
dfs(a1);
a2=p;
fi(0, n+1){vis[i]=0; dis1[i]=-1;}
dis1[a2]=0;
dfs1(a2);//calculating distance from a2(dis1[])
printf("Case %d:\n", cs++);
fi(0, n-1){
printf("%d\n", max(dis[i], dis1[i]));
vt[i].clear(); cost[i].clear();
}
}
return 0;
}
|
No comments:
Post a Comment