Submission #618077


Source Code Expand

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.PriorityQueue;

public class Main {
	InputStream is;

	int __t__ = 1;
	int __f__ = 0;
	int __FILE_DEBUG_FLAG__ = __f__;
	String __DEBUG_FILE_NAME__ = "src/D2";

	FastScanner in;
	PrintWriter out;
	
	/* -----------Dijkstra---------- */
	public class Edge {
		int to;
		int c;
		int sleepTo;
		int sleepCost;
		
		Edge(int to, int c, int sleepTo, int sleepCost) {
			this.to = to;
			this.c = c;
			this.sleepTo = sleepTo;
			this.sleepCost = sleepCost;
		}
		
		public String toString() {
			return "(" + to + "," + c + ")";
		}
	}

	public class Dijkstra {
		protected final static int INF = 1_000_000_000;
				
		class State implements Comparable<State> {
			int n;
			
			State(int n) {
				this.n = n;
			}

			public int compareTo(State s) {
				int c1 = res.minCost[n], c2 = res.minCost[s.n];
				if (c1 < c2) return -1;
				else if (c1 > c2) return 1;
				else return 0;
			}
		}
		
		DijkstraResult res;
		
		Dijkstra() {}
		
		/**
		 * This function is for Fixed Graph.
		 * The second Variable "edge" should be fixed graph which is prepared by called method.
		 * @param start root node.
		 * @param edge fixed edges.
		 * @return dijkstra result.
		 */
		DijkstraResult doit(int start, int[][] edge) {
			int n = edge.length;
			res = new DijkstraResult(n);
			Arrays.fill(res.minCost, Dijkstra.INF);
			
			PriorityQueue<State> pq = new PriorityQueue<State>();
			pq.add(new State(start));
			res.minCost[start] = 0;
			res.path[start] = start;
			
			while (!pq.isEmpty()) {
				State s = pq.poll();
				for (int i = 0; i < n; i++) {
					if (res.minCost[i] > res.minCost[s.n] + edge[s.n][i]) {
						res.minCost[i] = res.minCost[s.n] + edge[s.n][i];
						res.path[i] = s.n;
						pq.add(new State(i));
					}
				}
			}
			
			return res;
		}
		
		/**
		 * return the result of Dijkstra.
		 * This function is for Sparse Graph.
		 * The second Variable "edge" should be sparse graph which is prepared by called method.
		 * @param start root node
		 * @edge sparse graph.
		 * @return dijkstra result
		 */
		DijkstraResult doit(int start, ArrayList<Edge>[] edge) {
			int n = edge.length;
			res = new DijkstraResult(n);
			Arrays.fill(res.minCost, Dijkstra.INF);
			
			PriorityQueue<State> pq = new PriorityQueue<State>();
			pq.add(new State(start));
			res.minCost[start] = 0;
			res.path[start] = start;
			
			while (!pq.isEmpty()) {
				State s = pq.poll();
				for (Edge e : edge[s.n]) {
					if (res.minCost[e.to] > res.minCost[s.n] + e.c) {
						res.minCost[e.to] = res.minCost[s.n] + e.c;
						res.path[e.to] = s.n;
						pq.add(new State(e.to));
					}
				}
			}
			
			return res;
		}
	}

	/**
	 * it contains minCost and path from start node to each nodes.
	 * @author hiro116s
	 *
	 */
	class DijkstraResult {
		int[] minCost;
		int[] path;
		
		DijkstraResult(int n) {
			minCost = new int[n];
			path = new int[n];
		}
	}
	/*-------------end--------------*/

	class P implements Comparable<P> {
		int n;
		int cost;

		P(int n, int cost) {
			this.n = n;
			this.cost = cost;
		}
		
		P(int n, int c1, int c2) {
			this(n, Math.max(c1, c2));
		}
		
		public int compareTo(P s) {
			return cost - s.cost;
		}

		public String dump(String symbol) {
			return symbol + " : " + n + " " + cost;
		}
	}
	
	int MAX = 255000;
	void solve() {
		int N = in.nextInt(), M = in.nextInt(), src = in.nextInt(), dst = in.nextInt();
		int[] L = new int[M];
		int[][] s = new int[M][];
		int[][] w = new int[M][];
		for (int i = 0; i < M; i++) {
			L[i] = in.nextInt();
			s[i] = new int[L[i]];
			w[i] = new int[L[i]-1];
			for (int j = 0; j < L[i]; j++) {
				s[i][j] = in.nextInt();
			}
			for (int j = 0; j < L[i] - 1; j++) {
				w[i][j] = in.nextInt();
			}
		}
		ArrayList<Edge>[] g = new ArrayList[N];
		for (int i = 0; i < N; i++) {
			g[i] = new ArrayList<>();
		}
		
		int[] sum = new int[MAX];
		for (int i = 0; i < M; i++) {
			Arrays.fill(sum, 0);
			int n = L[i];			
			for (int j = 1; j < n; j++) {
				sum[j] = sum[j-1] + w[i][j-1];
			}
			for (int j = 0; j < n - 1; j++) {
				int from = s[i][j], to = s[i][j+1];
				g[to].add(new Edge(from, w[i][j], s[i][n-1], sum[n-1] - sum[j]));
				g[from].add(new Edge(to, w[i][j], s[i][0], sum[j+1]));
			}
		}
		
		long res = 0;
		int[] dmin = new Dijkstra().doit(dst, g).minCost;
		
		PriorityQueue<P> pq = new PriorityQueue<>();
		pq.add(new P(dst, 0));
		int[] minCost = new int[N];
		Arrays.fill(minCost, Dijkstra.INF);
		minCost[dst] = 0;
		
		while (!pq.isEmpty()) {
			P p = pq.poll();
			if (minCost[p.n] < p.cost) continue;
			minCost[p.n] = p.cost;
			for (Edge e : g[p.n]) {
				int ncost = Math.max(minCost[p.n] + e.c, dmin[e.sleepTo] + e.sleepCost);
				pq.add(new P(e.to, ncost));
			}
		}
		
		System.out.println(minCost[src]);
	}
	
	public void run() {
		if (__FILE_DEBUG_FLAG__ == __t__) {
			try {
				is = new FileInputStream(__DEBUG_FILE_NAME__);
			} catch (FileNotFoundException e) {
				// TODO 自動生成された catch ブロック
				e.printStackTrace();
			}
			System.out.println("FILE_INPUT!");
		} else {
			is = System.in;
		}
		in = new FastScanner(is);
		out = new PrintWriter(System.out);

		solve();
	}
	
	public static void main(String[] args) {
		new Main().run();
	}

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}

		System.out.println("----------------------------");
		System.out.println();
	}

	public void debug(Object... obj) {
		System.out.println(Arrays.deepToString(obj));
	}

	class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
			//stream = new FileInputStream(new File("dec.in"));

		}

		int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		int[] nextIntArray(int n) {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();

			return array;
		}

		int[][] nextIntMap(int n, int m) {
			int[][] map = new int[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextIntArray(m);
			}
			return map;
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		long[] nextLongArray(int n) {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();

			return array;
		}

		long[][] nextLongMap(int n, int m) {
			long[][] map = new long[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextLongArray(m);
			}
			return map;
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		double[] nextDoubleArray(int n) {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();

			return array;
		}

		double[][] nextDoubleMap(int n, int m) {
			double[][] map = new double[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextDoubleArray(m);
			}
			return map;
		}

		String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		String[] nextStringArray(int n) {
			String[] array = new String[n];
			for (int i = 0; i < n; i++)
				array[i] = next();

			return array;
		}

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}
}

Submission Info

Submission Time
Task C - メンテナンス明け
User hiro116s
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 8780 Byte
Status AC
Exec Time 988 ms
Memory 43644 KB

Compile Error

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Judge Result

Set Name Subtask1 Subtask2
Score / Max Score 50 / 50 50 / 50
Status
AC × 52
AC × 6
Set Name Test Cases
Subtask1 small/00_sample00, small/00_sample01, small/00_sample02, small/10_small-0000, small/10_small-0001, small/10_small-0002, small/10_small-0003, small/10_small-0004, small/10_small-0005, small/10_small-0006, small/10_small-0007, small/10_small-0008, small/10_small-0009, small/10_small-0010, small/10_small-0011, small/10_small-0012, small/10_small-0013, small/10_small-0014, small/10_small-0015, small/10_small-0016, small/10_small-0017, small/10_small-0018, small/10_small-0019, small/30_max_small, small/40_simple_0000, small/40_simple_0001, small/40_simple_0002, small/40_simple_0003, small/40_simple_0004, small/40_simple_0005, small/40_simple_0006, small/40_simple_0007, small/40_simple_0008, small/40_simple_0009, small/40_simple_0010, small/40_simple_0011, small/40_simple_0012, small/40_simple_0013, small/40_simple_0014, small/40_simple_0015, small/40_simple_0016, small/40_simple_0017, small/40_simple_0018, small/40_simple_0019, small/90_dijkstra_killer_00, small/90_dijkstra_killer_01, small/91_tayama_killer_00, small/91_tayama_killer_01, small/91_tayama_killer_02, small/91_tayama_killer_03, small/91_tayama_killer_04, small/91_tayama_killer_05
Subtask2 large/20_large-00, large/20_large-01, large/20_large-02, large/20_large-03, large/20_large-04, large/31_max_large
Case Name Status Exec Time Memory
large/20_large-00 AC 955 ms 43644 KB
large/20_large-01 AC 988 ms 42068 KB
large/20_large-02 AC 962 ms 41928 KB
large/20_large-03 AC 977 ms 42268 KB
large/20_large-04 AC 936 ms 42052 KB
large/31_max_large AC 715 ms 40500 KB
small/00_sample00 AC 373 ms 24532 KB
small/00_sample01 AC 359 ms 24520 KB
small/00_sample02 AC 371 ms 24516 KB
small/10_small-0000 AC 436 ms 24788 KB
small/10_small-0001 AC 383 ms 24796 KB
small/10_small-0002 AC 379 ms 24692 KB
small/10_small-0003 AC 377 ms 24700 KB
small/10_small-0004 AC 397 ms 24800 KB
small/10_small-0005 AC 373 ms 24768 KB
small/10_small-0006 AC 415 ms 24868 KB
small/10_small-0007 AC 375 ms 24760 KB
small/10_small-0008 AC 379 ms 24808 KB
small/10_small-0009 AC 379 ms 24876 KB
small/10_small-0010 AC 374 ms 24704 KB
small/10_small-0011 AC 385 ms 24800 KB
small/10_small-0012 AC 394 ms 24788 KB
small/10_small-0013 AC 416 ms 24884 KB
small/10_small-0014 AC 382 ms 24764 KB
small/10_small-0015 AC 396 ms 24732 KB
small/10_small-0016 AC 390 ms 24788 KB
small/10_small-0017 AC 395 ms 24764 KB
small/10_small-0018 AC 444 ms 24752 KB
small/10_small-0019 AC 406 ms 24728 KB
small/30_max_small AC 360 ms 24656 KB
small/40_simple_0000 AC 365 ms 24248 KB
small/40_simple_0001 AC 379 ms 24416 KB
small/40_simple_0002 AC 357 ms 24448 KB
small/40_simple_0003 AC 371 ms 24468 KB
small/40_simple_0004 AC 369 ms 24452 KB
small/40_simple_0005 AC 367 ms 24316 KB
small/40_simple_0006 AC 371 ms 24320 KB
small/40_simple_0007 AC 354 ms 24520 KB
small/40_simple_0008 AC 354 ms 24468 KB
small/40_simple_0009 AC 362 ms 24484 KB
small/40_simple_0010 AC 355 ms 24452 KB
small/40_simple_0011 AC 360 ms 24508 KB
small/40_simple_0012 AC 357 ms 24328 KB
small/40_simple_0013 AC 397 ms 24352 KB
small/40_simple_0014 AC 473 ms 24284 KB
small/40_simple_0015 AC 363 ms 24416 KB
small/40_simple_0016 AC 355 ms 24424 KB
small/40_simple_0017 AC 362 ms 24480 KB
small/40_simple_0018 AC 365 ms 24332 KB
small/40_simple_0019 AC 361 ms 24336 KB
small/90_dijkstra_killer_00 AC 381 ms 24496 KB
small/90_dijkstra_killer_01 AC 408 ms 24516 KB
small/91_tayama_killer_00 AC 352 ms 24528 KB
small/91_tayama_killer_01 AC 378 ms 24484 KB
small/91_tayama_killer_02 AC 360 ms 24328 KB
small/91_tayama_killer_03 AC 386 ms 24532 KB
small/91_tayama_killer_04 AC 385 ms 24264 KB
small/91_tayama_killer_05 AC 421 ms 24424 KB