Advertisement
Guest User

LateParty

a guest
Apr 24th, 2019
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.82 KB | None | 0 0
  1. import java.util.HashSet;
  2. import java.util.PriorityQueue;
  3. import java.util.Scanner;
  4. import java.util.Set;
  5. import java.util.Stack;
  6.  
  7. public class LateParty {
  8.     private static int I;
  9.     private static int S;
  10.     private static int F;
  11.     private static int[][] STREET_LIST;
  12.     private static int[] HOTEL_LIST;
  13.     private static Set<Integer>[] directions;
  14.     private static Set<Integer>[] origins;
  15.     private static long[] distances;
  16.     private static boolean[][] onTheWay;
  17.  
  18.     static class DistanceMap {
  19.  
  20.         static class Distance implements Comparable<Distance> {
  21.             private final int location;
  22.             private final long dist;
  23.  
  24.             Distance(int i, long d) {
  25.                 location = i;
  26.                 dist = d;
  27.             }
  28.  
  29.             boolean isSpurious() {
  30.                 return dist > distances[location];
  31.             }
  32.  
  33.             @Override
  34.             public int compareTo(Distance arg0) {
  35.                 long l = dist - arg0.dist;
  36.                 return (l == 0) ? location - arg0.location : (l < 0) ? -1 : 1;
  37.             }
  38.         }
  39.  
  40.         private static PriorityQueue<Distance> queue;
  41.  
  42.         static void setStructures() {
  43.             queue = new PriorityQueue<>();
  44.             setDistance(0, 0);
  45.             for (int i = 1; i < I; i++) {
  46.                 distances[i] = Long.MAX_VALUE;
  47.             }
  48.         }
  49.  
  50.         private static void setDistance(int i, long d) {
  51.             distances[i] = d;
  52.             queue.add(new Distance(i, d));
  53.         }
  54.  
  55.         private static boolean updateDistances() {
  56.             if (queue.isEmpty()) {
  57.                 return false;
  58.             }
  59.             Distance d = queue.poll();
  60.             if (!d.isSpurious()) {
  61.                 int i = d.location;
  62.                 for (int s : directions[i]) {
  63.                     int j = getGoal(i, s);
  64.                     long l = getDistance(i, s);
  65.                     if (l < distances[j]) {
  66.                         origins[j].clear();
  67.                         origins[j].add(i);
  68.                         setDistance(j, l);
  69.                     } else if (l == distances[j]) {
  70.                         origins[j].add(i);
  71.                     }
  72.                 }
  73.             }
  74.             return true;
  75.         }
  76.  
  77.         static void getDistances() {
  78.             while (updateDistances()) {
  79.             }
  80.         }
  81.     }
  82.  
  83.     private static void readInput() {
  84.         Scanner in = new Scanner(System.in);
  85.         I = in.nextInt();
  86.         S = in.nextInt();
  87.         F = in.nextInt();
  88.  
  89.         STREET_LIST = new int[S][3];
  90.         HOTEL_LIST = new int[F + 1];
  91.         for (int i = 0; i < S; i++) {
  92.             STREET_LIST[i][0] = in.nextInt();
  93.             STREET_LIST[i][1] = in.nextInt();
  94.             STREET_LIST[i][2] = in.nextInt();
  95.         }
  96.         for (int i = 0; i < F + 1; i++) {
  97.             HOTEL_LIST[i] = in.nextInt();
  98.         }
  99.         in.close();
  100.     }
  101.  
  102.     @SuppressWarnings("unchecked")
  103.     private static void setStructures() {
  104.         directions = (Set<Integer>[]) new Set<?>[I];
  105.         origins = (Set<Integer>[]) new Set<?>[I];
  106.         onTheWay = new boolean[2][I];
  107.         distances = new long[I];
  108.         for (int i = 0; i < I; i++) {
  109.             directions[i] = new HashSet<Integer>();
  110.             origins[i] = new HashSet<Integer>();
  111.             onTheWay[0][i] = false;
  112.             onTheWay[1][i] = false;
  113.         }
  114.         for (int i = 0; i < S; i++) {
  115.             directions[STREET_LIST[i][0]].add(i);
  116.             directions[STREET_LIST[i][1]].add(i);
  117.         }
  118.         onTheWay[0][0] = true;
  119.         onTheWay[1][0] = true;
  120.         DistanceMap.setStructures();
  121.     }
  122.  
  123.     private static int getGoal(int i, int s) {
  124.         return STREET_LIST[s][0] + STREET_LIST[s][1] - i;
  125.     }
  126.  
  127.     private static long getDistance(int i, int s) {
  128.         return STREET_LIST[s][2] + distances[i];
  129.     }
  130.  
  131.     private static void getWay(int test, int i) {
  132.         Stack<Integer> stack = new Stack<>();
  133.         stack.push(i);
  134.         while (!stack.isEmpty()) {
  135.             int j = stack.pop();
  136.             if (!onTheWay[test][j]) {
  137.                 onTheWay[test][j] = true;
  138.                 for (int u : origins[j]) {
  139.                     stack.push(u);
  140.                 }
  141.             }
  142.         }
  143.     }
  144.  
  145.     private static long maxCommonDistance() {
  146.         getWay(0, HOTEL_LIST[0]);
  147.         for (int i = 1; i < F + 1; i++) {
  148.             getWay(1, HOTEL_LIST[i]);
  149.         }
  150.         long max = 0;
  151.         for (int i = 1; i < I; i++) {
  152.             if (onTheWay[0][i] && onTheWay[1][i] && distances[i] > max) {
  153.                 max = distances[i];
  154.             }
  155.         }
  156.         return max;
  157.     }
  158.  
  159.     public static void main(String[] args) {
  160.         readInput();
  161.         setStructures();
  162.         DistanceMap.getDistances();
  163.         System.out.println(maxCommonDistance());
  164.     }
  165.  
  166. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement