简单题,bfs
使用快排时cmp函数写的不太熟练,记录一下
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #define INF 200000000 char ss[3][25]; int idx,flag; struct str { char s[25]; int lev; }sl[305]; int search(char sx[25]) { int i; if(strcmp(sx,sl[0].s)==0) flag=1; for(i=0;i<=idx;i++) { if(strcmp(sx,sl[i].s)==0) return i; } idx++; strcpy(sl[idx].s,sx); return idx; } int cmp(const void *a,const void *b) { int i; i=0; struct str *x=(struct str *)a; struct str *y=(struct str *)b; while((*x).s[i]!='\0'&&(*y).s[i]!='\0') { if((*x).s[i]>(*y).s[i]) return 1; if((*x).s[i]<(*y).s[i]) return -1; i++; } if((*x).s[i]=='\0') return -1; else return 1; } int main() { int map[305][305],n,i,j,k,l,queue[10001],a,b,c,begin,end,x; while(scanf("%d",&n)!=EOF) { flag=0; memset(map,0,sizeof(map)); memset(sl,-1,sizeof(sl)); strcpy(sl[0].s,"Isenbaev"); sl[0].lev=0; idx=0; for(i=0;i<n;i++) { scanf("%s",&ss[0]); a=search(ss[0]); scanf("%s",&ss[1]); b=search(ss[1]); scanf("%s",&ss[2]); c=search(ss[2]); map[a][b]=1; map[b][a]=1; map[a][c]=1; map[c][a]=1; map[b][c]=1; map[c][b]=1; } begin=0;end=1; queue[0]=0; while(begin!=end) { x=queue[begin]; begin++; for(i=1;i<=idx;i++) if(map[x][i]==1&&sl[i].lev==-1) { sl[i].lev=sl[x].lev+1; queue[end]=i; end++; } } qsort(sl,idx+1,sizeof(sl[0]),cmp); for(i=0;i<=idx;i++) { if(sl[i].lev!=-1) { if(strcmp(sl[i].s,"Isenbaev")!=0||strcmp(sl[i].s,"Isenbaev")==0&&flag==1) printf("%s %d\n",sl[i].s,sl[i].lev); } else printf("%s undefined\n",sl[i].s); } } return 0; }