学步园

TAG 搜索  dfs bfs

深度优先、宽度优先都行。

因为没有用STL 用静态数组分配节点，速度很不错  0.22 sec
808 KB

/* source code of submission 427641, Zhongshan University Online Judge System */<br /> #include <stdio.h><br /> #include <memory.h><br /> const int N=10000;<br /> struct tnode<br /> {<br /> int v,dist,next;<br /> };<br /> int dist[N];<br /> int g[N];<br /> bool visited[N];<br /> int n,k,ans;<br /> int a,b,c;<br /> tnode node[N*2];<br /> int nlen;<br /> void search(int root, int d )<br /> {<br /> bool isleaf=true;<br /> int p=g[root];<br /> while ( p!=-1)<br /> {<br /> if ( !visited[ node[p].v ] )<br /> {<br /> isleaf=false;<br /> visited[ node[p].v ]=true;<br /> search(node[p].v, d+node[p].dist );<br /> }<br /> p=node[p].next;<br /> }<br /> if ( isleaf )<br /> {<br /> ans= ans<d? d: ans;<br /> }<br /> }<br /> int main(int argc, char *argv[])<br /> {<br /> while ( scanf("%d%d", &n, &k)!=EOF )<br /> {<br /> nlen=-1;<br /> memset(g, -1, sizeof(g) );<br /> for (int i=0; i<n-1; ++i)<br /> {<br /> scanf("%d%d%d", &a, &b, &c);<br /> if ( a>b )<br /> {<br /> int tmp=a;<br /> a=b;<br /> b=tmp;<br /> }</p> <p> --a;<br /> --b;<br /> ++nlen;<br /> node[nlen].dist=c;<br /> node[nlen].v=b;<br /> node[nlen].next=g[a];<br /> g[a]=nlen;<br /> ++nlen;<br /> node[nlen].dist=c;<br /> node[nlen].v=a;<br /> node[nlen].next=g[b];<br /> g[b]=nlen;</p> <p> }<br /> ans=0;<br /> memset(visited, false, sizeof(visited) );<br /> visited[k-1]=true;<br /> search(k-1,0);<br /> printf("%d/n",ans );<br /> }<br /> return 0;<br /> }<br />