Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2020
244
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.67 KB | None | 0 0
  1. import javax.imageio.plugins.jpeg.JPEGImageReadParam;
  2. import javax.print.attribute.standard.MediaSize;
  3. import java.io.BufferedReader;
  4. import java.io.IOException;
  5. import java.io.InputStreamReader;
  6. import java.util.*;
  7.  
  8. public class Road {
  9. public static void main(String[] args) throws IOException {
  10. BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
  11. StringTokenizer tokenizer = new StringTokenizer(f.readLine());
  12. int n = Integer.parseInt(tokenizer.nextToken());
  13. int m = Integer.parseInt(tokenizer.nextToken());
  14. tokenizer = new StringTokenizer(f.readLine());
  15. int[][] distanceTo = new int[m][2];
  16. int[] islands = new int[m];
  17. for (int i = 0; i < m; i++) {
  18. islands[i] = Integer.parseInt(tokenizer.nextToken());
  19. }
  20. Arrays.sort(islands);
  21.  
  22. distanceTo[0][1] = islands[1];
  23. distanceTo[m - 1][0] = islands[m - 1] - islands[m - 2];
  24. for (int i = 1; i < m - 1; i++) {
  25. distanceTo[i][0] = islands[i] - islands[i - 1];
  26. distanceTo[i][1] = islands[i + 1] - islands[i];
  27. }
  28.  
  29. int[] distanceToLast = new int[m - 1];
  30. for (int i = 0; i < m - 1; i++) {
  31. distanceToLast[i] = islands[m - 1] - islands[i];
  32. }
  33.  
  34. tokenizer = new StringTokenizer(f.readLine());
  35. int g = Integer.parseInt(tokenizer.nextToken());
  36. int r = Integer.parseInt(tokenizer.nextToken());
  37.  
  38. islands = null;
  39. int[][] dp = new int[m][g + 1];
  40. for (int i = 0; i < m; i++) {
  41. Arrays.fill(dp[i], Integer.MAX_VALUE);
  42. }
  43.  
  44.  
  45. dp[0][0] = 0;
  46. Island start = new Island(0, 0, 0);
  47. PriorityQueue<Island> toCheck = new PriorityQueue<Island>();
  48. boolean[][] visited = new boolean[m][g + 1];
  49. toCheck.add(start);
  50. int minPossibleTimeSoFar = Integer.MAX_VALUE;
  51. while (!toCheck.isEmpty()) {
  52. Island island = toCheck.poll();
  53. if (visited[island.island][island.modTime]) {
  54. continue;
  55. }
  56. /*
  57. if (island.island == m - 1) {
  58. System.out.println(island.time);
  59. return;
  60. } */
  61. visited[island.island][island.modTime] = true;
  62. minPossibleTimeSoFar = Math.min(distanceToLast[island.island] + island.time, minPossibleTimeSoFar);
  63.  
  64. if (island.modTime == g) {
  65. int time = r + island.time;
  66. if (time < dp[island.island][0]) {
  67. dp[island.island][0] = time;
  68. toCheck.add(new Island(island.island, time, 0));
  69. }
  70. } else {
  71. if (island.modTime + distanceToLast[island.island] <= g && island.time + distanceToLast[island.island] <= minPossibleTimeSoFar) {
  72. System.out.println(island.time + distanceToLast[island.island]);
  73. return;
  74. }
  75.  
  76. int modTime = island.modTime + distanceTo[island.island][1];
  77.  
  78. if (island.island != m - 1 && modTime <= g) {
  79. int time = island.time + distanceTo[island.island][1];
  80. if (island.island + 1 == m - 1) {
  81. System.out.println(time);
  82. return;
  83. }
  84. if (time < dp[island.island + 1][modTime]) {
  85. dp[island.island + 1][modTime] = time;
  86. toCheck.add(new Island(island.island + 1, time, modTime));
  87. }
  88. }
  89.  
  90. modTime = island.modTime + distanceTo[island.island][0];
  91. if (island.island != 0 && modTime <= g) {
  92. int time = island.time + distanceTo[island.island][0];
  93. if (time < dp[island.island - 1][modTime]) {
  94. dp[island.island - 1][modTime] = time;
  95. toCheck.add(new Island(island.island - 1, time, modTime));
  96. }
  97. }
  98. }
  99. }
  100.  
  101. System.out.println(-1);
  102. }
  103.  
  104. private static class Island implements Comparable<Island> {
  105. int time;
  106. int modTime;
  107. int island;
  108.  
  109. public Island(int island, int time, int modTime) {
  110. this.island = island;
  111. this.time = time;
  112. this.modTime = modTime;
  113. }
  114.  
  115. @Override
  116. public int compareTo(Island island) {
  117. if (this.time < island.time) {
  118. return -1;
  119. } else if (this.time > island.time) {
  120. return 1;
  121. }
  122.  
  123. return 0;
  124. }
  125. }
  126. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement