Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.Scanner;
- //https://pastebin.com/CnimZXcj
- public class Lesson75 {
- public static int V;
- public static int[] maxCost;
- public static int[] parent;
- public static boolean[] mstSet;
- public static class Edge {
- int ev;
- int cost;
- public Edge(int ev, int cost) {
- this.ev = ev;
- this.cost = cost;
- }
- }
- public static ArrayList<Edge>[] map;
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- V = sc.nextInt();
- int E = sc.nextInt();
- int D = sc.nextInt();
- map = new ArrayList[V];
- for (int i=0; i<V; i++) {
- map[i] = new ArrayList<Edge>();
- }
- for (int i=0; i<E; i++) {
- int bv = sc.nextInt()-1;
- int ev = sc.nextInt()-1;
- int cost = sc.nextInt();
- map[bv].add(new Edge(ev, cost));
- map[ev].add(new Edge(bv, cost));
- }
- int[] destination = new int[D];
- for (int i=0; i<D; i++) {
- destination[i] = sc.nextInt()-1;
- }
- //Create parent
- //Create mstSet
- //Create lowCost
- maxCost = new int[V];
- parent = new int[V];
- mstSet = new boolean[V];
- Arrays.fill(maxCost, Integer.MIN_VALUE);
- Arrays.fill(parent, -1);
- maxCost[0] = Integer.MAX_VALUE; //choose 0 first
- for (int i=0; i<V; i++) {
- int u = maxKey();
- System.out.println(u);
- mstSet[u] = true;
- //How can you get the neighbors
- ArrayList<Edge> neighbor = map[u];
- for (Edge e:neighbor) {
- //e.ev is the neighbor vertice
- if (maxCost[e.ev]<e.cost && mstSet[e.ev]==false) {
- maxCost[e.ev] = e.cost;
- parent[e.ev] = u;
- }
- }
- }
- //loop all the destination cities
- int min = Integer.MAX_VALUE;
- boolean[] vis = new boolean[V];
- vis[0] = true;
- for (int i=0; i<D; i++) {
- int dest = destination[i];
- System.out.println(dest);
- while (dest!=-1 && !vis[dest]) { //not yet visit
- vis[dest] = true;
- if (min>maxCost[dest]) {
- min = maxCost[dest];
- }
- dest = parent[dest]; //reverse
- }
- }
- System.out.println(min);
- }
- public static int maxKey() {
- int max = Integer.MIN_VALUE;
- int maxIndex = -1;
- for (int i=0; i<V; i++) {
- if (maxCost[i]>max && mstSet[i]==false) {
- max= maxCost[i];
- maxIndex = i;
- }
- }
- return maxIndex;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement