2015
04-13

# CC On The Tree

CC lives on the tree which has N nodes.On every leaf of the tree there is an apple(leaf means there is only one branch connect this node ) .Now CC wants to get two apple ,CC can choose any node to start and the speed of CC is one meter per second.
now she wants to know the shortest time to get two apples;

Thers are many cases;
The first line of every case there is a number N(2<=N<=10000)
if n is 0 means the end of input.
Next there is n-1 lines,on the i+1 line there is three number ai,bi,ci
which means there is a branch connect node ai and node bi.
(1<=ai, bi<=N , 1<=ci<=2000)
ci means the len of the branch is ci meters ;

Thers are many cases;
The first line of every case there is a number N(2<=N<=10000)
if n is 0 means the end of input.
Next there is n-1 lines,on the i+1 line there is three number ai,bi,ci
which means there is a branch connect node ai and node bi.
(1<=ai, bi<=N , 1<=ci<=2000)
ci means the len of the branch is ci meters ;

7
1 2 1
2 3 2
3 4 1
4 5 1
3 6 3
6 7 4
0

5

#include <iostream>
#include <cstdio>

using namespace std;

const int inf=30000000;
const int maxx=10003;

struct Tree{
int v,we,next;
};

Tree tree[maxx*2];
int dp_f[maxx],dp_s[maxx];

tree[pt].v=y;
tree[pt].we=we;
}

int min(int a,int b){
return a<b?a:b;
}

void dfs(int root,int pre){//选出从每个根到其所有子树的叶子距离的最小值和次小值
bool mark=false;
int v=tree[i].v;
if(pre==v)continue;
mark=true;
dfs(v,root);
if(dp_f[root]>(dp_f[v]+tree[i].we)){
dp_s[root]=dp_f[root];
dp_f[root]=dp_f[v]+tree[i].we;
}else if(dp_f[root]==dp_f[v]+tree[i].we){
dp_s[root]=dp_f[root];
}else{
dp_s[root]=min(dp_s[root],dp_f[v]+tree[i].we);
}
}
if(!mark)dp_f[root]=dp_s[root]=0;
}

int main(){
int n;
while(scanf("%d",&n)&&n){
pt=1;
int i,x,y,we,cnt;
cnt=0;
for(i=1;i<=n;i++){
dp_f[i]=dp_s[i]=inf;
}
memset(tree,0,sizeof(tree));
for(i=2;i<=n;i++){
scanf("%d%d%d",&x,&y,&we);
if(x==1 || y==1)cnt++;//这个地方在考虑根节点是否为叶子的时候只判断了x而没有判断y，wa了三次。悲剧
}
dfs(1,0);//把1当作根节点深搜
int ans=1<<30;
for(i=1;i<=n;i++){//选一遍最小的就可以了
if(dp_f[i]==0 || dp_s[i]==0 ||dp_f[i]>20000000 ||dp_s[i]>20000000)continue;
ans=min(ans,dp_f[i]+dp_s[i]);
}
if(cnt==1)ans=min(ans,dp_f[1]);//如果根结点是叶子的话，还得判断一下根节点处的情况
printf("%d\n",ans);
}
return 0;
}

1. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;
{
degree[*j]++;
}
}

为什么每遍历一条链表，要首先将每个链表头的顶点的入度置为0呢？
比如顶点5，若在顶点1、2、3、4的链表中出现过顶点5，那么要增加顶点5的入度，但是在遍历顶点5的链表时，又将顶点5的入度置为0了，那之前的从顶点1234到顶点5的边不是都没了吗？

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

3. 第23行：
hash = -1是否应该改成hash[s ] = -1

因为是要把从字符串s的start位到当前位在hash中重置

修改提交后能accept，但是不修改居然也能accept