Advertisement
Guest User

Untitled

a guest
Aug 20th, 2019
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.26 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Scanner;
  4. //https://pastebin.com/CnimZXcj
  5. public class Lesson75 {
  6. public static int V;
  7. public static int[] maxCost;
  8. public static int[] parent;
  9. public static boolean[] mstSet;
  10. public static class Edge {
  11. int ev;
  12. int cost;
  13. public Edge(int ev, int cost) {
  14. this.ev = ev;
  15. this.cost = cost;
  16. }
  17. }
  18. public static ArrayList<Edge>[] map;
  19. public static void main(String[] args) {
  20. Scanner sc = new Scanner(System.in);
  21.  
  22. V = sc.nextInt();
  23. int E = sc.nextInt();
  24. int D = sc.nextInt();
  25.  
  26. map = new ArrayList[V];
  27. for (int i=0; i<V; i++) {
  28. map[i] = new ArrayList<Edge>();
  29. }
  30.  
  31. for (int i=0; i<E; i++) {
  32. int bv = sc.nextInt()-1;
  33. int ev = sc.nextInt()-1;
  34. int cost = sc.nextInt();
  35. map[bv].add(new Edge(ev, cost));
  36. map[ev].add(new Edge(bv, cost));
  37. }
  38.  
  39. int[] destination = new int[D];
  40. for (int i=0; i<D; i++) {
  41. destination[i] = sc.nextInt()-1;
  42. }
  43.  
  44. //Create parent
  45. //Create mstSet
  46. //Create lowCost
  47. maxCost = new int[V];
  48. parent = new int[V];
  49. mstSet = new boolean[V];
  50. Arrays.fill(maxCost, Integer.MIN_VALUE);
  51. Arrays.fill(parent, -1);
  52. maxCost[0] = Integer.MAX_VALUE; //choose 0 first
  53. for (int i=0; i<V; i++) {
  54. int u = maxKey();
  55. System.out.println(u);
  56. mstSet[u] = true;
  57. //How can you get the neighbors
  58. ArrayList<Edge> neighbor = map[u];
  59. for (Edge e:neighbor) {
  60. //e.ev is the neighbor vertice
  61. if (maxCost[e.ev]<e.cost && mstSet[e.ev]==false) {
  62. maxCost[e.ev] = e.cost;
  63. parent[e.ev] = u;
  64. }
  65. }
  66.  
  67. }
  68.  
  69. //loop all the destination cities
  70.  
  71. int min = Integer.MAX_VALUE;
  72. boolean[] vis = new boolean[V];
  73. vis[0] = true;
  74. for (int i=0; i<D; i++) {
  75. int dest = destination[i];
  76. System.out.println(dest);
  77. while (dest!=-1 && !vis[dest]) { //not yet visit
  78. vis[dest] = true;
  79. if (min>maxCost[dest]) {
  80. min = maxCost[dest];
  81. }
  82. dest = parent[dest]; //reverse
  83. }
  84. }
  85. System.out.println(min);
  86. }
  87.  
  88. public static int maxKey() {
  89. int max = Integer.MIN_VALUE;
  90. int maxIndex = -1;
  91. for (int i=0; i<V; i++) {
  92. if (maxCost[i]>max && mstSet[i]==false) {
  93. max= maxCost[i];
  94. maxIndex = i;
  95. }
  96. }
  97. return maxIndex;
  98. }
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement