Solution of Light OJ 1257 - Farthest Nodes in a Tree (II)

We may solve using BFS of DFS. Both solutions are given.
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; }

Solution of Light OJ 1066 - Gathering Food

/* Bismillahir Rahmanir Rahim Solution-Using BFS Apply BFS from every letter(not the last) orderly */ #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[130]; int sts[130], ar[27], cnt[130], vis[130], c, ans, n, fl; void bfs(int st, int en){ queue<int>q; q.push(st); fii(ii, 0, n*n) {vis[ii]=0, cnt[ii]=0;} vis[st]=1; while(!q.empty()){ int u=q.front(); q.pop(); for(int j=0; j<vt[u].size(); j++){ int v=vt[u][j]; //if(not visited && not '#' && not getter than the next letter) if(!vis[v]&&sts[v]!=-1&&sts[v]<=en){ if(sts[v]==en){ //if(find the letter) c=cnt[u]+1; return ; } else cnt[v]=cnt[u]+1; q.push(v); vis[v]=1; } } } } int main(){ int t, cs=1, cnt, m; cin>>t; while(t--){ cin>>n; cnt=0, ans=0, m=0; fii(i, 1, n){ fii(j, 1, n){ char ch; cin>>ch; cnt++; if(ch=='.') sts[cnt]=0; else if(ch=='#') sts[cnt]=-1; else{ int x=(ch-'A')+1; m=max(m, x); // highest letter sts[cnt]=x; ar[x]=cnt; //saving the position of letters } if(i>1){ vt[cnt].push_back(cnt-n); vt[cnt-n].push_back(cnt); } if(j>1){ vt[cnt].push_back(cnt-1); vt[cnt-1].push_back(cnt); } } } /* Input End */ cout<<"Case "<<cs++<<": "; fi(1, m-1){ c=0, fl=0; bfs(ar[i], i+1); // BFS for every letter(not last) if(c==0){ // if(fail to get next letter) fl=1; break; } else ans=ans+c; } if(fl) cout<<"Impossible"<<endl; else cout<<ans<<endl; fi(0, n*n) vt[i].clear(); } return 0; }

Solution of Light OJ 1111 - Best Picnic Ever

/* Bismillahir Rahmanir Rahim Solution-Using BFS */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) using namespace std; vector<int>vt[1009]; int ar[100], cnt[1009], vis[1009], n, m, k, ans; void bfs(int st){ fi( 0, n) vis[i]=0; vis[st]=1; queue<int>q; q.push(st); cnt[st]++; //counting-how many people reach here(this node) if(cnt[st]==k) ans++; //if(counter[this node]==total people) while(!q.empty()){ int u=q.front(); q.pop(); for(int j=0; j<vt[u].size(); j++){ int v=vt[u][j]; if(!vis[v]){ q.push(v); vis[v]=1; cnt[v]++; //same as previous if(cnt[v]==k) ans++; //same as previous } } } } int main(){ int t, cs=1, u, v; cin>>t; while(t--){ ans=0; cin>>k>>n>>m; fi(0, k-1) cin>>ar[i]; fi(1, m){ cin>>u>>v; vt[u].push_back(v); } fi(0, n) cnt[i]=0; for(int x=0; x<k; x++){ bfs(ar[x]); //BFS from all people location (node) } cout<<"Case "<<cs++<<": "<<ans<<endl; fi(0, n) vt[i].clear(); } return 0; }

Solution of Light OJ 1141 - Number Transformation

/* Bismillar Rahmanir Rahmanir Solution-Using BFS */ #include<bits/stdc++.h> using namespace std; vector<int>p_fact[1001]; int prime[200], t_case, t=1, a, b, cnt=0,ans, sz; bool num[501]; void sieve(){ for(int i=0; i<=500; i++)num[i]=true; for(int i=3; i*i<=500; i+=2){ if(num[i]){ for(int j=i*i; j<=500; j+=i*2) num[j]=false; } } int j=0; prime[j++]=2; for(int i=3; i<=500; i+=2){ if(num[i]){ cnt++; prime[j++]=i; } } } void prime_fact(){ //store the prime fact in every index number for(int i=0; i<cnt; i++){ for(int j=2; j*prime[i]<=1000; j++) p_fact[j*prime[i]].push_back(prime[i]); } } bool bfs(int x, int y){ int level[1009]={0}, xx, xxx; bool visit[1001]; memset(visit, false, sizeof(visit)); queue<int>q; q.push(x); level[x]=0; while(!q.empty()){ xx=q.front(); if(xx==y){ans=level[xx]; return true;} q.pop(); sz=p_fact[xx].size(); if(!visit[xx]){ for(int i=0; i<sz; i++){ xxx=xx+p_fact[xx][i]; if(xxx<=y){ if(!level[xxx]) level[xxx]=level[xx]+1; q.push(xxx); } if(xxx==y){ ans=level[xxx]; return true; } } visit[xx]=true; } } return false; } int main() { sieve(); prime_fact(); cin>>t_case; while(t_case--){ cin>>a>>b; if(bfs(a, b)) cout<<"Case "<<t++<<": "<<ans<<endl; else cout<<"Case "<<t++<<": -1"<<endl; } return 0; }