rally/ElectricRally_artur.java

  1 import java.util.Arrays;
  2 import java.util.Comparator;
  3 import java.util.LinkedList;
  4 import java.util.PriorityQueue;
  5 import java.util.Scanner;
  6 
  7 public class ElectricRally_artur {
  8   public static void main(String[] args) {
  9     Scanner in = new Scanner(System.in);
 10 
 11     while (true) {
 12       int n = in.nextInt(), m = in.nextInt();
 13       if (n == 0 && m == 0)
 14         break;
 15 
 16       LinkedList<Interval>[] a = new LinkedList[n];
 17       for (int i = 0; i < n; i++)
 18         a[i] = new LinkedList<Interval>();
 19 
 20       for (int i = 0; i < m; i++) {
 21         int p = in.nextInt(), q = in.nextInt();
 22         while (true) {
 23           int s = in.nextInt(), t = in.nextInt(), w = in.nextInt();
 24           if (w <= 240) {
 25             a[p].add(new Interval(q, s, t, w * 2));
 26             a[q].add(new Interval(p, s, t, w * 2));
 27           }
 28           if (t == 1439)
 29             break;
 30         }
 31       }
 32 
 33       int best = Integer.MAX_VALUE;
 34       final int[] dist = new int[n * 481], localtime = new int[n * 481];
 35       Arrays.fill(dist, Integer.MAX_VALUE);
 36 
 37       PriorityQueue<Integer> que = new PriorityQueue<Integer>(n, new Comparator<Integer>() {
 38         public int compare(Integer i, Integer j) {
 39           return dist[i] == dist[j] ? j - i : Integer.compare(dist[i], dist[j]);
 40         }
 41       });
 42 
 43       que.add(0 * 481 + 480);
 44       dist[que.peek()] = 0;
 45       localtime[que.peek()] = 720;
 46 
 47       while (!que.isEmpty()) {
 48         int p = que.poll();
 49         if (dist[p] > best)
 50           continue;
 51 
 52         int fuel = p % 481;
 53         int node = p / 481;
 54         if (node == n - 1)
 55           best = Math.min(best, dist[p]);
 56 
 57         for (Interval i : a[node]) {
 58           int wait = Math.max(i.distance - fuel, 0);
 59           int time = (localtime[p] + wait) % 1440;
 60           if (time < i.begin) {
 61             wait += i.begin - time;
 62             time = i.begin;
 63           }
 64           if (time > i.end) {
 65             wait += 1440 - time + i.begin;
 66             time = i.begin;
 67           }
 68 
 69           int total = dist[p] + wait + i.distance / 2;
 70           int newfuel = Math.min(wait + fuel, 480) - i.distance;
 71           int newnode = i.to * 481 + newfuel;
 72           if (dist[newnode] > total && total <= best) {
 73             dist[newnode] = total;
 74             localtime[newnode] = (time + i.distance / 2) % 1440;
 75             que.add(newnode);
 76           }
 77         }
 78       }
 79 
 80       System.out.println(best == Integer.MAX_VALUE ? 0 : best);
 81     }
 82   }
 83 
 84   static class Interval {
 85     int begin, end, distance, to;
 86 
 87     Interval(int v, int s, int t, int w) {
 88       to = v;
 89       begin = s;
 90       end = t;
 91       distance = w;
 92     }
 93   }
 94 }