How far away ?

这题明显的水题,一次编译就测试出来数据了..好吧,太简单了...

但我还是错了..

这题我用 MAP[40005][40005]数组调试的时候发现秒退问题.

因为以前经历过类似的,所以一下子就知道问题了;

以前看过过VECTOR的方法,所以我也改用向量问题;

完美解决..

 1 #include<iostream>  
 2 #include<vector>  
 3 #include<string.h>  
 4 using namespace std;  
 5 struct node  
 6 {  
 7     int pos;  
 8     int val;  
 9 }temp,q;  
10 vector<node>a[40005];  
11 int n,m,flag,e,vis[40005];  
12 void DFS(int s,int ans)  
13 {  
14     //printf("s=%d
",s);  
15     int size,i;  
16     if(vis[s]) return ;  //不访问重复的点
17     if(flag) return ;   //找到了就不继续找了;
18     if(s==e) {printf("%d
",ans);flag=1;return;}  
19      if(a[s].empty())  return ;  
20      else  
21      {  
22       vis[s]=1;  
23      size=a[s].size();  
24      for(i=0;i<size;i++)  
25         DFS(a[s][i].pos,ans+a[s][i].val);  
26      vis[s]=0;  
27      }  
28 }  
29 int main()  
30 {  
31     int cas;  
32     scanf("%d",&cas);  
33     while(cas--)  
34     {  
35         int i,j,x,y,z;  
36         scanf("%d %d",&n,&m);  
37         for(i=0;i<n-1;i++)  
38         {  
39                 scanf("%d %d %d",&x,&y,&z);  
40                 q.pos=y;q.val=z;  
41                 a[x].push_back(q);  
42                 q.pos=x;q.val=z;  
43                 a[y].push_back(q);  
44         }  
45         for(j=0;j<m;j++)  
46         {  
47             memset(vis,0,sizeof(vis));  
48             flag=0;  
49             int s;  
50             scanf("%d %d",&s,&e);  
51             DFS(s,0);  
52         }  
53         for(i=0;i<n;i++)  
54         {  
55             a[i].clear();  
56         }  
57     }  
58       return 0;  
59 }