#include<bits/stdc++.h> using namespace std; #define pb push_back class Graph{ int V; list<int>*adj; public: Graph(int V){this->V=V; adj=new list<int>[V]; } ~Graph() {delete []adj;} void addEdge(int u,int v){adj[u].pb(v); adj[v].pb(u); } void BFS(int s,int dest) { bool visited[V]; int parent[V]; memset(visited,false,sizeof(visited)); list<int>q; list<int>::iterator i; q.pb(s); visited[s]=true; parent[s]=s; while (!q.empty()) { s=q.front(); q.pop_front(); for (i=adj[s].begin();i!=adj[s].end();++i) { if (!visited[*i]) { q.pb(*i); parent[*i]=s; visited[*i]=true; if (*i==dest) { print(parent,dest); return; } } } } } void print(int parent[],int dest) { vector<int>path; while (parent[dest]!=dest) { path.pb(dest); dest=parent[dest]; } path.pb(dest); int l=path.size(); for (int i=l-1;i>-1;--i) printf("%C",path[i]+'A'); printf("\n"); } }; int main() { int tc,n,q,s,d; string a,b; scanf("%d",&tc); while (tc--) { Graph g(30); scanf("%d%d",&n,&q); getchar(); while (n--) { cin>>a>>b; s=a[0]-'A'; d=b[0]-'A'; g.addEdge(s,d); } while (q--) { cin>>a>>b; s=a[0]-'A'; d=b[0]-'A'; g.BFS(s,d); } if (tc) printf("\n"); } return 0; }
Wednesday, August 24, 2016
Published August 24, 2016 by Sourav Chowdhury with 0 comment
Published August 24, 2016 by Sourav Chowdhury with 0 comment
#include<bits/stdc++.h> using namespace std; #define pb push_back class Graph{ int V; list<int>*adj; public: Graph(int V){this->V=V; adj=new list<int>[V];} ~Graph(){delete []adj;} void addEdge(int u,int v){ adj[u].pb(v);} void BFS(int s) { if (adj[s].size()==0) {printf("0\n"); return;} bool visited[V]; memset(visited,false,sizeof(visited)); int level[V]; int cnt[V]={0}; list<int>q; list<int>::iterator i; q.pb(s); visited[s]=true; level[s]=0; int d,m=0; while (!q.empty()) { s=q.front(); q.pop_front(); cnt[level[s]]++; for (i=adj[s].begin();i!=adj[s].end();++i) { if (!visited[*i]) { q.pb(*i); visited[*i]=true; level[*i]=level[s]+1; } } } for (int j=1;j<=level[s];j++) if (m<cnt[j]) { m=cnt[j]; d=j; } printf("%d %d\n",m,d); return; } }; int main() { int e; while (scanf("%d",&e)!=EOF) { Graph g(e); int n,v; for (int i=0;i<e;i++) { scanf("%d",&n); while (n--) { scanf("%d",&v); g.addEdge(i,v); } } int t,s; scanf("%d",&t); while (t--) { scanf("%d",&s); g.BFS(s); } } return 0; }
Published August 24, 2016 by Sourav Chowdhury with 0 comment
#include<bits/stdc++.h> using namespace std; #define pb push_back map<string,int>msi; map<int,string>mis; class Graph{ int V; list<int>*adj; public: Graph(int V){this->V=V; adj=new list<int>[V]; } ~Graph() {delete []adj;} void addEdge(int u,int v){adj[u].pb(v); adj[v].pb(u); } void BFS(int s,int dest) { bool visited[V]; int parent[V]; memset(visited,false,sizeof(visited)); list<int>q; list<int>::iterator i; q.pb(s); visited[s]=true; parent[s]=s; while (!q.empty()) { s=q.front(); q.pop_front(); for (i=adj[s].begin();i!=adj[s].end();++i) { if (!visited[*i]) { q.pb(*i); parent[*i]=s; visited[*i]=true; if (*i==dest) { print(parent,dest); return; } } } } printf("No route\n"); } void print(int parent[],int dest) { vector<int>path; while (parent[dest]!=dest) { path.pb(dest); dest=parent[dest]; } path.pb(dest); int l=path.size(); for (int i=l-1;i>0;--i) cout<<mis[path[i]]<<" "<<mis[path[i-1]]<<endl; } }; int main() { int n,f=0; string a,b; while (scanf("%d",&n)!=EOF) { Graph g(2000); getchar(); int ind=-1; while (n--) { cin>>a>>b; if (msi.find(a)==msi.end()) { msi[a]=++ind; mis[ind]=a; } if (msi.find(b)==msi.end()) { msi[b]=++ind; mis[ind]=b; } g.addEdge(msi[a],msi[b]); } cin>>a>>b; if (f) cout<<endl; if (msi.find(a)==msi.end() || msi.find(b)==msi.end()) printf("No route\n"); else g.BFS(msi[a],msi[b]); f=1; msi.clear(); mis.clear(); } return 0; }
Published August 24, 2016 by Sourav Chowdhury with 0 comment
#include<bits/stdc++.h> using namespace std; #define pb push_back class Graph{ int V; list<int>*adj; public: Graph(int V); ~Graph(); void addEdge(int u, int v); void BFS(int s,int dest); }; Graph::Graph(int V) //construtor { this->V=V; adj=new list<int >[V]; } Graph::~Graph() //destructor { delete []adj; } void Graph::addEdge(int u,int v) { adj[u].pb(v); } void Graph::BFS(int s,int dest) { bool visited[V]; int parent[V]; memset(visited,false,sizeof(visited)); list<int>q; list<int>::iterator i; q.pb(s); visited[s]=true; parent[s]=s; while (!q.empty()) { s=q.front(); q.pop_front(); for (i=adj[s].begin();i!=adj[s].end();++i) { if (!visited[*i]) { q.pb(*i); visited[*i]=true; parent[*i]=s; if (*i==dest) { vector<int>path; int t=*i; while (parent[t]!=t) { path.pb(t); t=parent[t]; } path.pb(t); t=path.size(); for (int j=t-1;j>-1;j--) { printf("%d",path[j]); if (j) printf(" "); else printf("\n"); } return; } } } } printf("connection impossible\n"); return; } int main() { int routers; while (scanf("%d",&routers)!=EOF) { Graph g(routers+1); char s[1000]; getchar(); while (routers--) { gets(s); char *pch; pch=strtok(s,"-,"); int id=atoi(pch); pch=strtok(NULL,"-,"); while (pch!=NULL) { int sees=atoi(pch); g.addEdge(id,sees); pch=strtok(NULL,"-,"); } } int m; scanf("%d",&m); printf("-----\n"); while (m--) { int s,dest; scanf("%d%d",&s,&dest); g.BFS(s,dest); } } return 0; }
Published August 24, 2016 by Sourav Chowdhury with 0 comment
#include<bits/stdc++.h> using namespace std; #define pb push_back class Graph{ int V; list<int>*adj; public: Graph(int V); ~Graph(); void addEdge(int u, int v); int BFS(int s,int dest); }; Graph::Graph(int V) //construtor { this->V=V; adj=new list<int >[V]; } Graph::~Graph() //destructor { delete []adj; } void Graph::addEdge(int u,int v) { adj[u].pb(v); adj[v].pb(u); } int Graph::BFS(int s,int dest) { bool visited[V]; int level[V]; memset(visited,false,sizeof(visited)); list<int>q; list<int>::iterator i; q.pb(s); visited[s]=true; level[s]=0; while (!q.empty()) { s=q.front(); q.pop_front(); for (i=adj[s].begin();i!=adj[s].end();++i) { if (!visited[*i]) { q.pb(*i); visited[*i]=true; level[*i]=level[s]+1; if (*i==dest) return level[*i]; } } } return -1; } bool ifSuccessive(string a,string b) { if (a.length()!=b.length()) return false; int dif=0,l=a.length(); for (int i=0;i<l;i++) if (a[i]!=b[i]) dif++; return dif==1?true:false; } int main() { int tc; scanf("%d",&tc); while (tc--) { string s; map<string,int>msi; vector<string>v; int k=0; while (cin>>s) { if (s=="*") break; v.pb(s); msi[s]=k++; } Graph g(k); for (int i=0;i<k;i++) for (int j=i+1;j<k;j++) if (ifSuccessive(v[i],v[j])) g.addEdge(msi[v[i]],msi[v[j]]); string start,to,line; size_t pos; getline(cin,line); getline(cin,line); while(line != ""){ pos = line.find(" "); start = line.substr(0,pos); to = line.substr(pos+1,line.size()); cout<<start<<" "<<to<<" "<<g.BFS(msi[start],msi[to])<<endl; if(!getline(cin,line)) break; } if (tc) cout<<endl; } return 0; }
Published August 24, 2016 by Sourav Chowdhury with 0 comment
#include<bits/stdc++.h> using namespace std; #define pb push_back class Graph{ int V; list<int>*adj; public: Graph(int V); ~Graph(); void addEdge(int u, int v); int BFS(int s,int dest); }; Graph::Graph(int V) //construtor { this->V=V; adj=new list<int >[V]; } Graph::~Graph() //destructor { delete []adj; } void Graph::addEdge(int u,int v) { adj[u].pb(v); } int Graph::BFS(int s,int dest) { bool visited[V]; int level[V]; memset(visited,false,sizeof(visited)); list<int>q; list<int>::iterator i; q.pb(s); visited[s]=true; level[s]=0; while (!q.empty()) { s=q.front(); q.pop_front(); for (i=adj[s].begin();i!=adj[s].end();++i) { if (!visited[*i]) { q.pb(*i); visited[*i]=true; level[*i]=level[s]+1; if (*i==dest) return level[*i]; } } } return -1; } int main() { int tc,c=1; scanf("%d",&tc); printf("SHIPPING ROUTES OUTPUT\n"); while (tc--) { printf("\nDATA SET %d\n\n",c++); int m,n,p; scanf("%d%d%d",&m,&n,&p); Graph g(m); map<string,int>mp; string s,s1; getchar(); for (int i=0;i<m;i++) { cin>>s; mp[s]=i; } while (n--) { cin>>s>>s1; g.addEdge(mp[s],mp[s1]); g.addEdge(mp[s1],mp[s]); } while (p--) { int a; scanf("%d\n",&a); cin>>s>>s1; int l=g.BFS(mp[s],mp[s1]); if (l==-1) printf("NO SHIPMENT POSSIBLE\n"); else printf("$%d\n",a*l*100); } } printf("\nEND OF OUTPUT\n"); return 0; }
Subscribe to:
Comments (Atom)
