比赛 noip2016普及练习2 评测结果
题目名称 保卫钓鱼岛! 最终得分 0
用户昵称 jjky 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2016-11-07 21:12:36
显示代码纯文本
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<iostream>
  5. #include<algorithm>
  6. #include<map>
  7. #include<queue>
  8. #include<vector>
  9. using namespace std;
  10. const int maxn=10010,maxm=100010;
  11. int head[maxn],cn,n,m,sum,num;
  12. bool flag;
  13. long long he;
  14. struct date
  15. {
  16. int to,next;
  17. long long co;
  18. }edge[maxm];
  19. void addedge(int a,int b,int c)
  20. {
  21. edge[cn].to=b;
  22. edge[cn].next=head[a];
  23. edge[cn].co=c;
  24. head[a]=cn++;
  25. }
  26. int read()
  27. {
  28. int x=0;
  29. char ch;
  30. ch=getchar();
  31. while(ch<'0'||ch>'9')
  32. ch=getchar();
  33. while(ch>='0'&&ch<='9')
  34. {
  35. x=x*10+ch-'0';
  36. ch=getchar();
  37. }
  38. return x;
  39. }
  40. void dfs(int cur,int v,long long cost)
  41. {
  42. if(cur==v)
  43. {
  44. flag=1;
  45. sum=cost;
  46. return ;
  47. }
  48. int i,to,c;
  49. for(i=head[cur];i!=-1;i=edge[i].next)
  50. {
  51. to=edge[i].to;
  52. c=edge[i].co;
  53. if(flag==1)
  54. return ;
  55. dfs(to,v,cost+c);
  56. }
  57. return ;
  58. }
  59. int main()
  60. {
  61. freopen("diaoyu.in","r",stdin);
  62. freopen("diaoyu.out","w",stdout);
  63. int a,b,t,u,v;
  64. n=read();m=read();
  65. memset(head,-1,sizeof(head));
  66. for(int i=1;i<n;i++)
  67. {
  68. a=read();b=read();t=read();
  69. addedge(a,b,t);
  70. }
  71. for(int i=1;i<=m;i++)
  72. {
  73. u=read();v=read();
  74. flag=0;
  75. sum=0;
  76. dfs(u,v,0);
  77. if(flag==1)
  78. {
  79. num++;
  80. he+=sum;
  81. }
  82. }
  83. printf("%d\n%d",num,he);
  84. }
  85. /*
  86. 6 2
  87. 1 2 1
  88. 2 4 1
  89. 2 5 1
  90. 5 6 1
  91. 1 3 1
  92. 2 6
  93. 4 5
  94.  
  95. 1
  96. 2
  97. */
  98.