Solution of Light OJ 1099 - Not the Best

/* Bismillahir Rahmanir Rahim Solution-Using Dijkstra. Calculate shortest path and second shortest path for each node */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define ll long long using namespace std; vector<ll>vt[5009], cost[5009]; ll n, en, d1[5009], d2[5009], sz; //d2[]=second shortest, d1[]=shortest struct node{ ll u, w; node(ll a, ll b){ u=a, w=b; } bool operator < (const node & p)const{ return p.w<w; } }; void dijkstra(int st){ priority_queue<node>q; q.push(node(st, 0)); fi(1, n){d1[i]=30000000, d2[i]=30000000;} d1[st]=0; while(!q.empty()){ node top=q.top(); q.pop(); int u=top.u; sz=vt[u].size(); fi(0, sz-1){ int v=vt[u][i]; int uu=cost[u][i]; // mind it if(d1[u]+uu<d1[v]){ ll temp=d1[v]; d1[v]=d1[u]+uu; d2[v]=min(temp, min(d2[v], min(d2[u]+uu, d1[u]+3*uu))); q.push(node(v, d1[v]+d2[v])); } else if(d1[u]+uu<d2[v] && (d1[u]+uu)>d1[v]){ d2[v]=d1[u]+uu; } else{ d2[v]=min(d2[v], min(d2[u]+uu, d1[u]+3*uu)); } } } } int main(){ int t, cs=1, st, e, u, v, w, nn, ans; cin>>t; while(t--){ cin>>n>>e; fi(1, e){ cin>>u>>v>>w; vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } ll back=100000009; // Its for a special case, given bellow fi(0, vt[1].size()-1){ back=min(back, 2*cost[1][i]); } dijkstra(1); back=d1[n]+back; cout<<"Case "<<cs++<<": "<<min(back, d2[n])<<endl; fi(0, n){ vt[i].clear(); cost[i].clear(); } } return 0; } /* Special Case Input: 1 4 5 1 2 3 2 3 7 3 4 4 1 2 4 4 1 4 Output: Case 1: 10 */

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; }