Advertisement
Guest User

Untitled

a guest
Dec 11th, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.45 KB | None | 0 0
  1. import java.io.BufferedWriter;
  2. import java.io.DataInputStream;
  3. import java.io.IOException;
  4. import java.io.OutputStreamWriter;
  5. import java.io.PrintWriter;
  6. import java.util.ArrayList;
  7. import java.util.Arrays;
  8.  
  9. public class dmopc18c4p5 {
  10. static class Edge {
  11. int ev, cost, uses, used, initial;
  12.  
  13. public Edge(int ev, int cost, int uses, int used, int initial) {
  14. this.ev = ev;
  15. this.cost = cost;
  16. this.uses = uses;
  17. this.used = used;
  18. this.initial = initial;
  19. }
  20. }
  21.  
  22. static ArrayList<Edge>[] a;
  23. static int max, start;
  24. static int[] vis;
  25. static boolean[] vis1;
  26.  
  27. @SuppressWarnings("unchecked")
  28. public static void main(String[] args) throws IOException {
  29. int n = readInt(), k = readInt();
  30. a = new ArrayList[n + 1];
  31. vis = new int[n + 1];
  32. Arrays.fill(vis, 1);
  33. for (int i = 0; i < n + 1; i++) {
  34. a[i] = new ArrayList<Edge>();
  35. }
  36. for (int i = 0; i < k; i++) {
  37. int x = readInt();
  38. vis[x - 1] = 2;
  39. }
  40. for (int i = 0; i < n - 1; i++) {
  41. int c1 = readInt(), c2 = readInt(), cost = readInt();
  42. if (vis[i] == 2) {
  43. a[c1].add(new Edge(c2, cost, 2, 0, 2));
  44. a[c2].add(new Edge(c1, cost, 2, 0, 2));
  45. } else {
  46. a[c1].add(new Edge(c2, cost, 1, 0, 1));
  47. a[c2].add(new Edge(c1, cost, 1, 0, 1));
  48. }
  49. }
  50. vis1 = new boolean[n + 1];
  51. max = 0;
  52. for (int i = 1; i <= n; i++) {
  53. longest(i, 0);
  54. }
  55. System.out.println(max);
  56. }
  57.  
  58. public static int longest(int x, int d) {
  59. // System.out.println(x + " " + d);
  60. if (d > max) {
  61. max = d;
  62. }
  63. for (Edge e : a[x]) {
  64. if (e.used < e.uses) {
  65. e.used++;
  66. for (Edge v : a[e.ev]) {
  67. if (v.ev == x) {
  68. v.used++;
  69. }
  70. }
  71. longest(e.ev, d + e.cost);
  72. e.used--;
  73. for (Edge v : a[e.ev]) {
  74. if (v.ev == x) {
  75. v.used--;
  76. }
  77. }
  78. }
  79. }
  80. return max;
  81. }
  82.  
  83. final private static int BUFFER_SIZE = 1 << 16;
  84. private static DataInputStream din = new DataInputStream(System.in);
  85. private static byte[] buffer = new byte[BUFFER_SIZE];
  86. private static int bufferPointer = 0, bytesRead = 0;
  87. static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  88.  
  89. public static String readLine() throws IOException {
  90. byte[] buf = new byte[1000000]; // line length
  91. int cnt = 0, c;
  92. while ((c = Read()) != -1) {
  93. if (c == '\n')
  94. break;
  95. buf[cnt++] = (byte) c;
  96. }
  97. return new String(buf, 0, cnt);
  98. }
  99.  
  100. public static String read() throws IOException {
  101. byte[] ret = new byte[1024];
  102. int idx = 0;
  103. byte c = Read();
  104. while (c <= ' ') {
  105. c = Read();
  106. }
  107. do {
  108. ret[idx++] = c;
  109. c = Read();
  110. } while (c != -1 && c != ' ' && c != '\n' && c != '\r');
  111. return new String(ret, 0, idx);
  112. }
  113.  
  114. public static int readInt() throws IOException {
  115. int ret = 0;
  116. byte c = Read();
  117. while (c <= ' ')
  118. c = Read();
  119. boolean neg = (c == '-');
  120. if (neg)
  121. c = Read();
  122. do {
  123. ret = ret * 10 + c - '0';
  124. } while ((c = Read()) >= '0' && c <= '9');
  125.  
  126. if (neg)
  127. return -ret;
  128. return ret;
  129. }
  130.  
  131. public static long readLong() throws IOException {
  132. long ret = 0;
  133. byte c = Read();
  134. while (c <= ' ')
  135. c = Read();
  136. boolean neg = (c == '-');
  137. if (neg)
  138. c = Read();
  139. do {
  140. ret = ret * 10 + c - '0';
  141. } while ((c = Read()) >= '0' && c <= '9');
  142. if (neg)
  143. return -ret;
  144. return ret;
  145. }
  146.  
  147. public static double readDouble() throws IOException {
  148. double ret = 0, div = 1;
  149. byte c = Read();
  150. while (c <= ' ')
  151. c = Read();
  152. boolean neg = (c == '-');
  153. if (neg)
  154. c = Read();
  155.  
  156. do {
  157. ret = ret * 10 + c - '0';
  158. } while ((c = Read()) >= '0' && c <= '9');
  159.  
  160. if (c == '.') {
  161. while ((c = Read()) >= '0' && c <= '9') {
  162. ret += (c - '0') / (div *= 10);
  163. }
  164. }
  165.  
  166. if (neg)
  167. return -ret;
  168. return ret;
  169. }
  170.  
  171. private static void fillBuffer() throws IOException {
  172. bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  173. if (bytesRead == -1)
  174. buffer[0] = -1;
  175. }
  176.  
  177. private static byte Read() throws IOException {
  178. if (bufferPointer == bytesRead)
  179. fillBuffer();
  180. return buffer[bufferPointer++];
  181. }
  182.  
  183. public void close() throws IOException {
  184. if (din == null)
  185. return;
  186. din.close();
  187. }
  188.  
  189. static void print(Object o) {
  190. pr.print(o);
  191. }
  192.  
  193. static void println(Object o) {
  194. pr.println(o);
  195. }
  196.  
  197. static void flush() {
  198. pr.flush();
  199. }
  200.  
  201. static void println() {
  202. pr.println();
  203. }
  204.  
  205. static void exit() throws IOException {
  206. din.close();
  207. pr.close();
  208. System.exit(0);
  209. }
  210. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement