Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.HashSet;
- import java.util.PriorityQueue;
- import java.util.Scanner;
- import java.util.Set;
- import java.util.Stack;
- public class LateParty {
- private static int I;
- private static int S;
- private static int F;
- private static int[][] STREET_LIST;
- private static int[] HOTEL_LIST;
- private static Set<Integer>[] directions;
- private static Set<Integer>[] origins;
- private static long[] distances;
- private static boolean[][] onTheWay;
- static class DistanceMap {
- static class Distance implements Comparable<Distance> {
- private final int location;
- private final long dist;
- Distance(int i, long d) {
- location = i;
- dist = d;
- }
- boolean isSpurious() {
- return dist > distances[location];
- }
- @Override
- public int compareTo(Distance arg0) {
- long l = dist - arg0.dist;
- return (l == 0) ? location - arg0.location : (l < 0) ? -1 : 1;
- }
- }
- private static PriorityQueue<Distance> queue;
- static void setStructures() {
- queue = new PriorityQueue<>();
- setDistance(0, 0);
- for (int i = 1; i < I; i++) {
- distances[i] = Long.MAX_VALUE;
- }
- }
- private static void setDistance(int i, long d) {
- distances[i] = d;
- queue.add(new Distance(i, d));
- }
- private static boolean updateDistances() {
- if (queue.isEmpty()) {
- return false;
- }
- Distance d = queue.poll();
- if (!d.isSpurious()) {
- int i = d.location;
- for (int s : directions[i]) {
- int j = getGoal(i, s);
- long l = getDistance(i, s);
- if (l < distances[j]) {
- origins[j].clear();
- origins[j].add(i);
- setDistance(j, l);
- } else if (l == distances[j]) {
- origins[j].add(i);
- }
- }
- }
- return true;
- }
- static void getDistances() {
- while (updateDistances()) {
- }
- }
- }
- private static void readInput() {
- Scanner in = new Scanner(System.in);
- I = in.nextInt();
- S = in.nextInt();
- F = in.nextInt();
- STREET_LIST = new int[S][3];
- HOTEL_LIST = new int[F + 1];
- for (int i = 0; i < S; i++) {
- STREET_LIST[i][0] = in.nextInt();
- STREET_LIST[i][1] = in.nextInt();
- STREET_LIST[i][2] = in.nextInt();
- }
- for (int i = 0; i < F + 1; i++) {
- HOTEL_LIST[i] = in.nextInt();
- }
- in.close();
- }
- @SuppressWarnings("unchecked")
- private static void setStructures() {
- directions = (Set<Integer>[]) new Set<?>[I];
- origins = (Set<Integer>[]) new Set<?>[I];
- onTheWay = new boolean[2][I];
- distances = new long[I];
- for (int i = 0; i < I; i++) {
- directions[i] = new HashSet<Integer>();
- origins[i] = new HashSet<Integer>();
- onTheWay[0][i] = false;
- onTheWay[1][i] = false;
- }
- for (int i = 0; i < S; i++) {
- directions[STREET_LIST[i][0]].add(i);
- directions[STREET_LIST[i][1]].add(i);
- }
- onTheWay[0][0] = true;
- onTheWay[1][0] = true;
- DistanceMap.setStructures();
- }
- private static int getGoal(int i, int s) {
- return STREET_LIST[s][0] + STREET_LIST[s][1] - i;
- }
- private static long getDistance(int i, int s) {
- return STREET_LIST[s][2] + distances[i];
- }
- private static void getWay(int test, int i) {
- Stack<Integer> stack = new Stack<>();
- stack.push(i);
- while (!stack.isEmpty()) {
- int j = stack.pop();
- if (!onTheWay[test][j]) {
- onTheWay[test][j] = true;
- for (int u : origins[j]) {
- stack.push(u);
- }
- }
- }
- }
- private static long maxCommonDistance() {
- getWay(0, HOTEL_LIST[0]);
- for (int i = 1; i < F + 1; i++) {
- getWay(1, HOTEL_LIST[i]);
- }
- long max = 0;
- for (int i = 1; i < I; i++) {
- if (onTheWay[0][i] && onTheWay[1][i] && distances[i] > max) {
- max = distances[i];
- }
- }
- return max;
- }
- public static void main(String[] args) {
- readInput();
- setStructures();
- DistanceMap.getDistances();
- System.out.println(maxCommonDistance());
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement