If you write on c++ you can do this: char dot; unsigned int x,ip; ip = 0; for (int i = 24; i >= 8; i -= 8) { cin >> x >> dot; x <<= i; ip |= x; } cin >> x; ip |= x; ------------------ Now you have ip, same you can read mask. Edited by author 21.01.2019 14:50 Edited by author 21.01.2019 14:52 To read IP address /subnet mask I recommend you to use the following template unsigned int read_mask(){ unsigned int a, b, c, d; scanf("%u.%u.%u.%u", &a, &b, &c, &d); return (a<<24) + (b<<16) + (c<<8) + d; } my code: WA on test 3 typedef uint32_t bitmap_t; typedef struct { int val[ST_SIZE]; int head; } stack_t; typedef struct { int V; /*vertex*/ int *p; /*parent*/ char *c; /*color*/ int *d; /*distance*/ bitmap_t *adj; /*adjacency matrix*/ } graph_t; typedef struct { unsigned int ip; unsigned int mask; } nic_t; typedef struct { int nnic; nic_t nic[MAX_NIC]; } host_t; int main(void) { int i, j, c, m, n, k; char ip[16]; char mask[16]; host_t *hosts; graph_t *gr; scanf("%d", &n); hosts = malloc(sizeof(host_t) * n); for (i = 0; i < n; i++) { scanf("%d", &k); hosts[i].nnic = k; for (j = 0; j < k; j++) { scanf("%s", ip); scanf("%s", mask); hosts[i].nic[j].ip = str2ip(ip); hosts[i].nic[j].mask = str2ip(mask); } } gr = initgraph(n); for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { for (c = 0; c < hosts[i].nnic; c++) { for (m = 0; m < hosts[j].nnic; m++) { if ((hosts[i].nic[c].ip & hosts[i].nic[c].mask) == (hosts[j].nic[m].ip & hosts[j].nic[m].mask)) { setadj(gr, i, j); } } } } } /* for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { printf("%2d", (chkadj(gr, i, j)?1:0)); } printf("\n"); } */ int sp, ep; scanf("%d%d", &sp, &ep); --sp; --ep; bfs(gr, ep); if (gr->c[sp] == WHITE) { printf("No\n"); exit(0); } printf("Yes\n"); print_path(gr, sp, ep); printf("\n"); return 0; } void bfs(graph_t *gr, int sv) { if (gr->V == 0) return; int i, u, v; for (i = 0; i < gr->V; i++) { gr->c[i] = WHITE; gr->d[i] = INFTY; gr->p[i] = NPARENT; } enqueue(sv); gr->d[sv] = 0; gr->c[sv] = GREY; for (; dequeue(&u);) { for (i = 0; i < gr->V; i++) { if (chkadj(gr, u, i)) { v = i; if (gr->c[v] == WHITE) { gr->p[v] = u; gr->d[v] = gr->d[u] + 1; gr->c[v] = GREY; enqueue(v); } } } } } void print_path(graph_t *gr, int sv, int ev) { printf("%d ", sv + 1); if (sv == ev) { return; } else { print_path(gr, gr->p[sv], ev); } } graph_t *initgraph(int V) { graph_t *gr; if ((gr = malloc(sizeof(graph_t))) == NULL) return NULL; gr->V = V; gr->adj = initadj(gr); gr->p = malloc(sizeof(int) * V); gr->c = malloc(sizeof(int) * V); gr->d = malloc(sizeof(int) * V); if (!gr->adj || !gr->p || !gr->c || !gr->d) return NULL; return gr; } stack_t st_in; stack_t st_out; int push(stack_t *st, int val) { if (st->head == ST_SIZE) { return ERR; /*stack full*/ } st->val[st->head] = val; st->head++; return SUCC; } int pop(stack_t *st, int *val) { if (st->head == 0) { return ERR; } else { st->head--; *val = st->val[st->head]; return SUCC; } } int enqueue(int val) { if (push(&st_in, val) == ERR) { return ERR; } else { return SUCC; } } int dequeue(int *val) { int tmp; if (pop(&st_out, &tmp) == ERR) { /*empty st_out*/ if (pop(&st_in, &tmp) == ERR) { /*empty st_in*/ return ERR; } else { push(&st_out, tmp); } for (;;) { if (pop(&st_in, &tmp) == ERR) { break; } else { push(&st_out, tmp); } } pop(&st_out, val); return SUCC; } else { *val = tmp; return SUCC; } } bitmap_t *initadj(graph_t *gr) { int len; int V = gr->V; len = V * V / 2 - V / 2; return calloc(sizeof(bitmap_t), len / INT_BIT + 1); } bool chkadj(graph_t *gr, int row, int col) { int n = gr->V, tmp1, tmp2; tmp1 = row, tmp2 = col; row = MAX(tmp1, tmp2); col = MIN(tmp1, tmp2); return gr->adj[(row * n + col) / INT_BIT] & (1 << (row * n + col) % INT_BIT); } void setadj(graph_t *gr, int row, int col) { int n = gr->V, tmp1, tmp2; tmp1 = row, tmp2 = col; row = MAX(tmp1, tmp2); col = MIN(tmp1, tmp2); gr->adj[(row * n + col) / INT_BIT] = gr->adj[(row * n + col) / INT_BIT] | (1 << (row * n + col) % INT_BIT); } void deladj(graph_t *gr, int row, int col) { int n = gr->V, tmp1, tmp2; tmp1 = row, tmp2 = col; row = MAX(tmp1, tmp2); col = MIN(tmp1, tmp2); gr->adj[(row * n + col) / INT_BIT] = gr->adj[(row * n + col) / INT_BIT] & ~(1 << (row * n + col) % INT_BIT); } unsigned int str2ip(char *str) { unsigned int r, b; for (r = 0, b = 0; *str != '\0'; str++) { if (*str == '.') { str++; r = r << 8; r += b; b = 0; } b = b * 10 + (*str - '0'); } r = r << 8; r += b; return r; } what data test 2, because i being error wa 2 ai bít lỗi trên la gì không ? hep me!!! Help me!, I got WA 5!. :-s stuck in WA5 too>"< can't understand I use dijkstra algo, what's wrong? code #include <cstdio> #include <vector> #include <map> #include <set> using namespace std; const long long INF=100000000; typedef unsigned long long ULL; typedef pair<long long,long long> pii; typedef vector<vector<long long> > VVI; typedef vector<long long> vi; typedef map<long long,vi> MIV; MIV network; VVI G; long long n=1,n_int; void init_vert(){ for (long long i=0;i<=n;++i){ vector< long long > temp; G.push_back(temp); } for (MIV::iterator it=network.begin();it!=network.end();++it){ for(vi::iterator vit=it->second.begin();vit!=it->second.end();++vit){ for(vi::iterator vit2=it->second.begin();vit2!=it->second.end();++vit2){ G[*vit].push_back(*vit2); } } } } long long read_network(){ long long res=0; long long mask=0; long r1,r2,r3,r4; long m1,m2,m3,m4; scanf("%ld.%ld.%ld.%ld",&r1,&r2,&r3,&r4); scanf("%ld.%ld.%ld.%ld",&m1,&m2,&m3,&m4); res+=r1&m1;res<<8; res+=r2&m2;res<<8; res+=r3&m3;res<<8; res+=r4&m4; return res; } vector<long long> dist,parent; void dejkstra(long long s){ dist.assign(n+1,INF); parent.assign(n+1,INF); dist[s]=0; set<pair<long long,long long> > q; q.insert(make_pair(dist[s],s)); while (!q.empty()){ long long v=q.begin()->second; q.erase(q.begin()); for (size_t j=0;j<G[v].size();++j){ long long to=G[v][j]; if (dist[v]+1<dist[to]){ q.erase(make_pair(dist[to],to)); dist[to]=dist[v]+1; parent[to]=v; q.insert(make_pair(dist[to],to)); } } } } int main(){ //freopen("in","r",stdin); scanf("%lld",&n); long long n_n_m=0; for (size_t i=0;i<n;++i){ scanf("%lld",&n_int); for (size_t j=0;j<n_int;++j){ n_n_m=read_network(); network[n_n_m].push_back(i+1); } } init_vert(); long long _beg,_end; scanf("%lld%lld",&_beg,&_end); dejkstra(_beg); if (dist[_end]==INF){ printf("No\n"); return 0; } else{ printf("Yes\n"); long long p=_end; vector<long long>res; printf("%lld ",_beg); while(p!=_beg){ // printf(">>>%d\n",p); res.push_back(p); p=parent[p]; } for (vi::reverse_iterator it=res.rbegin();it!=res.rend();++it){ printf("%lld ",*it); } printf("\n"); } return 0; } #include <cstdio> #include <vector> #include <map> #include <set> using namespace std; const long long INF=10000; typedef unsigned long long ULL; typedef unsigned long UL; typedef pair<int,int> pii; typedef vector<int> vi; int n=0,n_int=0; vector<pair<int,int> > G; map<UL,vi > network; void init_vert(){ for (map<UL,vi >::iterator it=network.begin();it!=network.end();++it){ for(vi::iterator vit=it->second.begin();vit!=it->second.end();++vit){ for(vi::iterator vit2=it->second.begin();vit2!=it->second.end();++vit2){ if ( ( *vit ) != ( *vit2 ) ){ G.push_back(make_pair(*vit,*vit2)); } } }
} } UL read_network(){ UL res=0; long r1,r2,r3,r4; long m1,m2,m3,m4; scanf("%ld.%ld.%ld.%ld",&r1,&r2,&r3,&r4); scanf("%ld.%ld.%ld.%ld",&m1,&m2,&m3,&m4); res+=r1&m1;res<<4; res+=r2&m2;res<<4; res+=r3&m3;res<<4; res+=r4&m4; return res; } vector<long> dist; vector<int> parent; void FB(int start,int end){ dist.assign(n,INF); parent.assign(n,-1); dist[start]=0; for (size_t i=0;i<n;++i){ for (vector<pair<int,int> >::iterator it=G.begin();it!=G.end();++it){ if (dist[it->first]<INF){ if(dist[it->second]>dist[it->first]+1){
dist[it->second]=dist[it->first]+1; parent[it->second]=it->first; } } } } }
int main(){ freopen("in","r",stdin); scanf("%d",&n); UL n_n_m=0;
for (size_t i=0;i<n;++i){ scanf("%d",&n_int); for (size_t j=0;j<n_int;++j){ n_n_m=read_network(); network[n_n_m].push_back(i); } } init_vert(); int _beg,_end;
scanf("%d%d",&_beg,&_end);
FB(_beg-1,_end-1);
if (parent[_end-1]==-1){ printf("No\n"); return 0; } else{ printf("Yes\n"); int p=_end-1; vector<int> res; while(p!=_beg-1){ res.push_back(p); p=parent[p]; } printf("%d ",_beg); for (vi::reverse_iterator it=res.rbegin();it!=res.rend();++it){ printf("%d ",(*it)+1); } printf("\n"); } return 0; } res<<4 => res<<=4 + AC) hi Lex why res<<=4 hi Lex why res<<=4 a<<=8 <==> a = a<<8 Edited by author 28.11.2012 19:53My code... #include <iostream> #include <string> using namespace std; struct LAN { int somay; char **IP; char **Sub; }; int ChungMang(int a, int b, LAN *L); void Dijkstra(LAN *L, int d[], int prev[], int label[], int dau, int cuoi, int somang,int &kq); void Show(int dau, int cuoi, int prev[]); void main () { int somang; cin>>somang; LAN *L; L= new LAN[somang+1]; for(int i =1;i<=somang;i++) { cin>>L[i].somay; L[i].IP=new char*[L[i].somay]; L[i].Sub=new char*[L[i].somay]; for(int j = 0;j<L[i].somay;j++) { L[i].IP[j]=new char[100]; L[i].Sub[j]=new char[100]; cin>>L[i].IP[j]>>L[i].Sub[j]; } } int dau, cuoi; cin>>dau>>cuoi; int d[91]; int prev[91]; int label[91]; int kq=1; Dijkstra(L,d,prev,label,dau,cuoi,somang,kq); if(kq==0) return; cout<<"Yes\n"; Show(dau,cuoi,prev); } void Init(int d[], int prev[], int label[], int n, int dau) { for(int i=1; i<=n;i++) { d[i]=-1; prev[i]=-2; label[i]=1; } d[dau]=0; } void Dijkstra(LAN *L, int d[], int prev[], int label[], int dau, int cuoi, int somang,int &kq) { Init(d,prev,label,somang,dau); while(label[cuoi]==1) { int iMin = -1; int v = -1; for(int i=1;i<=somang;i++) { if(label[i]==1 && d[i]!=-1&&(d[i]<iMin||iMin==-1)) { iMin = d[i]; v=i; } } if(iMin == -1) { cout<<"No"; kq =0; break; } d[v]=iMin; label[v]=0; for(int j=1;j<=somang;j++) { if(label[j]==1&& ChungMang(v,j,L)==1) { d[j]=d[v]+1; prev[j]=v; } } } } int Test(char *IP3, char *IP4, char *Sub3, char *Sub4) { char *IP1 = IP3; char *IP2=IP4; char *Sub1= Sub3; char *Sub2=Sub4; int i=0; int nIP=0; int nSub=0; while(nIP!=3) { if(IP1[i]=='.') nIP++; i++; } nIP=i; i=0; while(nSub!=3) { if(Sub1[i]=='.') nSub++; i++; } nSub=i; IP1[nIP]='\0'; IP2[nIP]='\0'; Sub1[nSub]='\0'; Sub2[nSub]='\0'; if(strcmp(IP1,IP2)==0&&strcmp(Sub1,Sub2)==0) return 1; return 0; } int ChungMang(int a, int b, LAN *L) { int giong=0; for(int i=0;i<L[a].somay;i++) { for(int j = 0;j<L[b].somay;j++) { if(Test(L[a].IP[i],L[b].IP[j],L[a].Sub[i],L[b].Sub[j])) return 1; } } return 0; } void Show(int dau, int cuoi, int prev[]) { int temp[100]; int i=99; int k = cuoi; cout<<dau; while (k != dau) { temp[i]=k; k=prev[k]; i--; } for(int j = i+1;j<100;j++) {
cout<<" "<<temp[j]; cout<<endl; } } In the sample input, there is an extra space in the third line from the bottom (i.e. after the number '1'). Because there are no extra spaces in the actual tests, this extra space is better removed cuz people who use strict char by char reading (like me) might freak out fora while. i think there are something wrong with the example: the 6th computer: it's ip address should be 195.38.54.65, but not 195.38.54.94. Actually it could not have 195.38.54.65 because same address assigned to 5'th computer. But they both belongs to the same subnet: 65 & 224 == 94 & 224 == 64 I'm sorry. I just made a stupid mistake: I use 195038054094&255255255224 directly,so I get a wrong answer. thank you for help! Edited by author 08.04.2011 01:22 2 1 1.1.1.1 1.1.1.1 1 1.1.1.1 1.1.1.1 1 1 This test is incorrect... It is my program. program sad; var tu:array[1..100,1..100] of int64; d,p:array[1..1000] of int64; f:array[1..1000] of boolean; k,pre,pree:array[1..1000] of int64; a:array[1..90,1..6,1..8] of int64; ii,jj,w,i,j,m,n,u,v,bit,l,r,t,q,sum,g,i1,i2,i3,i4,n1,n2,n3,n4:longint; c:char;s:string; function pd:boolean; var w:longint; begin for w:=1 to 4 do if a[i,j,w]<>a[ii,jj,w] then exit(false); exit(true); end; procedure spfa(s:longint); var i,j,k,h,t,x:longint; begin fillchar(f,sizeof(f),false); fillchar(p,sizeof(p),0); for i:=1 to n do d[i]:=maxlongint shr 1; f[s]:=true; t:=1; h:=0; d[s]:=0; p[t]:=s; while h<>t do begin h:=(h mod n)+1; x:=p[h]; f[x]:=false; for j:=1 to n do if (tu[x,j]<>0) and (d[x]+tu[x,j]<d[j]) then begin d[j]:=d[x]+tu[x,j]; if not f[j] then begin t:=(t mod n) +1; p[t]:=j; f[j]:=true; pre[j]:=x; end; end; end; end; begin readln(n); for i:=1 to n do begin readln(k[i]); for j:=1 to k[i] do begin readln(s); g:=pos('.',s);val(copy(s,1,g-1),i1);delete(s,1,g); g:=pos('.',s);val(copy(s,1,g-1),i2);delete(s,1,g); g:=pos('.',s);val(copy(s,1,g-1),i3);delete(s,1,g); g:=pos(' ',s);val(copy(s,1,g-1),i4);delete(s,1,g); g:=pos('.',s);val(copy(s,1,g-1),n1);delete(s,1,g); g:=pos('.',s);val(copy(s,1,g-1),n2);delete(s,1,g); g:=pos('.',s);val(copy(s,1,g-1),n3);delete(s,1,g); val(s,n4); a[i,j,1]:=i1 and n1; a[i,j,2]:=i2 and n2; a[i,j,3]:=i3 and n3; a[i,j,4]:=i4 and n4; end; end; for i:=1 to n do for ii:=1 to n do for j:=1 to k[i] do for jj:=1 to k[ii] do begin if not pd then break; tu[i,ii]:=1; tu[ii,i]:=1; end; readln(l,r); spfa(l); q:=r; sum:=0; while q<>0 do begin inc(sum); pree[sum]:=q; q:=pre[q]; end; if (sum>1) and (sum<>0) then begin writeln('Yes'); for i:=sum downto 1 do write(pree[i],' '); end else write('No'); writeln; end. WA at 5# ~~ Help me~! I think, that there was no adjustment to the "order of the computers" for output in problem "Output" paragraph. I think, that it was no difference between direct path and reverse path. So, for example code, that printed Yes 1 3 5 6 was Accepted, but code, that printed Yes 6 5 3 1 was rejected. Maybe you can show me your code? And weren't you training for the National Day last night? strange.. Edited by author 06.09.2009 17:24 me too! i have found it! check if your code is longint or int64 Edited by author 10.02.2010 19:05 |
|