結果

問題 No.1 道のショートカット
ユーザー atn112323atn112323
提出日時 2016-02-06 13:28:56
言語 Java19
(openjdk 21)
結果
AC  
実行時間 96 ms / 5,000 ms
コード長 12,850 bytes
コンパイル時間 2,397 ms
コンパイル使用メモリ 92,564 KB
実行使用メモリ 53,508 KB
最終ジャッジ日時 2023-09-27 21:51:57
合計ジャッジ時間 6,427 ms
ジャッジサーバーID
(参考情報)
judge11 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
49,284 KB
testcase_01 AC 42 ms
49,364 KB
testcase_02 AC 41 ms
49,732 KB
testcase_03 AC 41 ms
49,272 KB
testcase_04 AC 41 ms
49,308 KB
testcase_05 AC 41 ms
49,428 KB
testcase_06 AC 41 ms
49,496 KB
testcase_07 AC 42 ms
49,304 KB
testcase_08 AC 88 ms
52,788 KB
testcase_09 AC 86 ms
52,528 KB
testcase_10 AC 86 ms
52,588 KB
testcase_11 AC 88 ms
52,092 KB
testcase_12 AC 93 ms
53,508 KB
testcase_13 AC 96 ms
53,100 KB
testcase_14 AC 51 ms
50,516 KB
testcase_15 AC 43 ms
49,508 KB
testcase_16 AC 69 ms
51,216 KB
testcase_17 AC 44 ms
49,352 KB
testcase_18 AC 49 ms
50,392 KB
testcase_19 AC 51 ms
48,676 KB
testcase_20 AC 58 ms
50,412 KB
testcase_21 AC 55 ms
51,468 KB
testcase_22 AC 51 ms
50,344 KB
testcase_23 AC 91 ms
52,584 KB
testcase_24 AC 82 ms
52,924 KB
testcase_25 AC 61 ms
50,476 KB
testcase_26 AC 53 ms
50,420 KB
testcase_27 AC 90 ms
53,072 KB
testcase_28 AC 44 ms
49,504 KB
testcase_29 AC 66 ms
51,276 KB
testcase_30 AC 53 ms
48,500 KB
testcase_31 AC 58 ms
50,240 KB
testcase_32 AC 92 ms
52,788 KB
testcase_33 AC 84 ms
52,492 KB
testcase_34 AC 81 ms
52,956 KB
testcase_35 AC 53 ms
50,524 KB
testcase_36 AC 62 ms
50,248 KB
testcase_37 AC 55 ms
50,472 KB
testcase_38 AC 46 ms
49,432 KB
testcase_39 AC 56 ms
51,056 KB
testcase_40 AC 53 ms
51,304 KB
testcase_41 AC 44 ms
49,464 KB
testcase_42 AC 41 ms
49,308 KB
testcase_43 AC 43 ms
49,512 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

	/**
	 * This class represents a problem setting.
	 */
	class Problem implements IProblem {

		int N;
		int C;
		int V;
		int[] S, T, Y, M;
		
		@Override
		public void set(ProblemReader reader) throws IOException {
			N = reader.nextInt();
			C = reader.nextInt();
			V = reader.nextInt();
			S = reader.nextIntArray();
			T = reader.nextIntArray();
			Y = reader.nextIntArray();
			M = reader.nextIntArray();
		}
		
		@Override
		public String toString() {
			StringBuilder sb = new StringBuilder();
			sb.append(StringUtils.toString(N) + "\n");
			sb.append(StringUtils.toString(C) + "\n");
			sb.append(StringUtils.toString(V) + "\n");
			sb.append(StringUtils.toString(S) + "\n");
			sb.append(StringUtils.toString(T) + "\n");
			sb.append(StringUtils.toString(Y) + "\n");
			sb.append(StringUtils.toString(M));
			return sb.toString();
		}
	}
	
	/**
	 * Solver for the problem.
	 * It's the most important part of codes in this file.
	 */
	class Solver implements IProblemSolver<Problem> {

		int inf = 1000000000;
		
		@Override
		public String solve(Problem problem) {
			int N = problem.N, C = problem.C, V = problem.V;
			int[] S = problem.S, T = problem.T, Y = problem.Y, M = problem.M;
			return StringUtils.toString(solve(N, C, V, S, T, Y, M));
		}
		
		private int solve(int N, int C, int V, int[] S, int[] T, int[] Y, int[] M) {
			City[] cities = new City[N];
			for (int i = 0; i < N; i++) {
				cities[i] = new City();
			}
			for (int i = 0; i < V; i++) {
				Edge edge = new Edge(S[i] - 1, T[i] - 1, Y[i], M[i]);
				cities[edge.s].edges.add(edge);
			}
			int[][] dp = new int[N][C + 1];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j <= C; j++) {
					dp[i][j] = inf;
				}
			}
			dp[0][0] = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j <= C; j++) {
					for (Edge edge : cities[i].edges) {
						int c = j + edge.y;
						if (c <= C) {
							dp[edge.t][c] = Math.min(dp[edge.t][c], dp[i][j] + edge.m);
						}
					}
				}
			}
			int min = -1;
			for (int i = 0; i <= C; i++) {
				if (dp[N - 1][i] < inf) {
					if (min == -1 || dp[N - 1][i] < min) {
						min = dp[N - 1][i];
					}
				}
			}
			return min;
		}
		
		class Edge {
			
			int s, t, y, m;
			
			Edge(int s, int t, int y, int m) {
				this.s = s;
				this.t = t;
				this.y = y;
				this.m = m;
			}
		}
		
		class City {
			
			List<Edge> edges = new ArrayList<>();
		}
	}
	
	/**
	 * This class is a solver to confirm the main solver.
	 * This solver often works only for a problem with a small number setting.
	 */
	class Solver2 implements IProblemSolver<Problem> {

		@Override
		public String solve(Problem problem) {
			// TODO
			return null;
		}
	}
	
	class Factory implements IProblemFactory<Problem> {

		@Override
		public Problem newProblem() {
			// TODO
			return null;
		}

		@Override
		public Problem newProblem(ProblemReader reader) throws IOException {
			Problem problem = new Problem();
			problem.set(reader);
			return problem;
		}
	}
	
	ProblemProcessor<Problem> processor;
	
	Main() {
		Init();
	}
	
	void Init() {
		ProblemProcessorConfig<Problem> config = new ProblemProcessorConfig<>();
		
		config.factory = new Factory();
		config.solver = new Solver();
		config.solver2 = new Solver2();
		
		processor = new ProblemProcessor<Problem>(config);
	}
	
	void process(String mode) throws IOException {
		processor.process(mode);
	}
	
	public static void main(String args[]) throws IOException {
		String mode = "solve";
		new Main().process(mode);
	}
	
/*
	Common library
*/
	
	interface IProblem {
		
		abstract void set(ProblemReader reader) throws IOException;
	}
	
	interface IProblemFactory<P extends IProblem> {
		
		abstract P newProblem();
		abstract P newProblem(ProblemReader reader) throws IOException;
	}
	
	interface IProblemSolver<P extends IProblem> {
		
		abstract String solve(P problem);
	}
	
	class ProblemReader {
		
		BufferedReader br = null;
		
		ProblemReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		int nextInt() throws IOException {
			return StringUtils.toInt(br.readLine());
		}
		
		long nextLong() throws IOException {
			return StringUtils.toLong(br.readLine());
		}
		
		double nextDouble() throws IOException {
			return StringUtils.toDouble(br.readLine());
		}
		
		String nextString() throws IOException {
			return br.readLine();
		}
		
		int[] nextIntArray() throws IOException {
			return StringUtils.toIntArray(br.readLine());
		}
		
		long[] nextLongArray() throws IOException {
			return StringUtils.toLongArray(br.readLine());
		}
		
		double[] nextDoubleArray() throws IOException {
			return StringUtils.toDoubleArray(br.readLine());
		}
		
		String[] nextStringArray() throws IOException {
			return StringUtils.toStringArray(br.readLine());
		}
		
		int[] nextIntArray(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextInt();
			}
			return a;
		}
		
		long[] nextLongArray(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextLong();
			}
			return a;
		}
		
		double[] nextDoubleArray(int n) throws IOException {
			double[] a = new double[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextDouble();
			}
			return a;
		}
		
		String[] nextStringArray(int n) throws IOException {
			String[] strs = new String[n];
			for (int i = 0; i < n; i++) {
				strs[i] = nextString();
			}
			return strs;
		}
		
		int[][] nextIntArray2(int n) throws IOException {
			int[][] a = new int[n][];
			for (int i = 0; i < n; i++) {
				a[i] = nextIntArray();
			}
			return a;
		}
		
		long[][] nextLongArray2(int n) throws IOException {
			long[][] a = new long[n][];
			for (int i = 0; i < n; i++) {
				a[i] = nextLongArray();
			}
			return a;
		}
		
		double[][] nextDoubleArray2(int n) throws IOException {
			double[][] a = new double[n][];
			for (int i = 0; i < n; i++) {
				a[i] = nextDoubleArray();
			}
			return a;
		}
		
		String[][] nextStringArray2(int n) throws IOException {
			String[][] strs = new String[n][];
			for (int i = 0; i < n; i++) {
				strs[i] = nextStringArray();
			}
			return strs;
		}
		
		void close() throws IOException {
			if (br != null) {
				br.close();
			}
		}
	}
	
	class ProblemCreator<P extends IProblem> {
		
		IProblemFactory<P> factory;
		
		ProblemCreator(IProblemFactory<P> factory) {
			this.factory = factory;
		}
		
		void create() throws FileNotFoundException {
			P problem = factory.newProblem();
			System.out.println(problem.toString());
		}
	}
	
	class ProblemSolverComparator<P extends IProblem> {
		
		IProblemFactory<P> factory;
		IProblemSolver<P> solver1, solver2;
		
		ProblemSolverComparator(IProblemFactory<P> factory, IProblemSolver<P> solver1, IProblemSolver<P> solver2) {
			this.factory = factory;
			this.solver1 = solver1;
			this.solver2 = solver2;
		}
		
		void compare() throws IOException {
			ProblemReader reader = null;
			try {
				reader = new ProblemReader();
				P problem = factory.newProblem(reader);
				String res1 = solver1.solve(problem);
				String res2 = solver2.solve(problem);
				if (res1.equals(res2)) {
					System.out.println(res1);
				} else {
					System.err.println(res1 + " " + res2);
				}
			} finally {
				if (reader != null) {
					reader.close();
				}
			}
		}
	}
	
	class ProblemAnswerer<P extends IProblem> {
		
		IProblemFactory<P> factory;
		IProblemSolver<P> solver;
		
		ProblemAnswerer(IProblemFactory<P> factory, IProblemSolver<P> solver) {
			this.factory = factory;
			this.solver = solver;
		}
		
		void answer() throws IOException {
			ProblemReader reader = null;
			try {
				reader = new ProblemReader();
				P problem = factory.newProblem(reader);
				String res = solver.solve(problem);
				System.out.println(res);
			} finally {
				if (reader != null) {
					reader.close();
				}
			}
		}
	}
	
	class ProblemProcessorConfig<P extends IProblem> {
		
		IProblemFactory<P> factory;
		
		IProblemSolver<P> solver, solver2;
	}
	
	class ProblemProcessor<P extends IProblem> {
		
		ProblemProcessorConfig<P> config;
		
		ProblemCreator<P> creator;
		ProblemSolverComparator<P> comparator;
		ProblemAnswerer<P> answerer;
		
		ProblemProcessor(ProblemProcessorConfig<P> config) {
			this.config = config;
			creator = new ProblemCreator<P>(config.factory);
			comparator = new ProblemSolverComparator<P>(config.factory, config.solver, config.solver2);
			answerer = new ProblemAnswerer<P>(config.factory, config.solver);
		}
		
		void process(String mode) throws IOException {
			switch (mode) {
			case "create":
				creator.create();
				break;
			case "debug":
				comparator.compare();
				break;
			case "solve":
				answerer.answer();
				break;
			}
		}
	}
	
	static class StringUtils {
		
		static String toString(int a) {
			return String.valueOf(a);
		}
		
		static String toString(long a) {
			return String.valueOf(a);
		}
		
		static String toString(double a) {
			return String.valueOf(a);
		}
		
		static String toString(String str) {
			return str;
		}
		
		static String toString(int[] a) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < a.length; i++) {
				if (i < a.length - 1) {
					sb.append(a[i] + " ");
				} else {
					sb.append(a[i]);
				}
			}
			return sb.toString();
		}
		
		static String toString(long[] a) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < a.length; i++) {
				if (i < a.length - 1) {
					sb.append(a[i] + " ");
				} else {
					sb.append(a[i]);
				}
			}
			return sb.toString();
		}
		
		static String toString(double[] a) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < a.length; i++) {
				if (i < a.length - 1) {
					sb.append(a[i] + " ");
				} else {
					sb.append(a[i]);
				}
			}
			return sb.toString();
		}
		
		static String toString(String[] strs) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < strs.length; i++) {
				if (i < strs.length - 1) {
					sb.append(strs[i] + " ");
				} else {
					sb.append(strs[i]);
				}
			}
			return sb.toString();
		}
		
		static String toString(int[][] a) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < a[i].length; j++) {
					if (j < a[i].length - 1) {
						sb.append(a[i][j] + " ");
					} else {
						sb.append(a[i][j]);
					}
				}
				sb.append("\n");
			}
			sb.setLength(sb.length() - 1);
			return sb.toString();
		}
		
		static String toString(long[][] a) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < a[i].length; j++) {
					if (j < a[i].length - 1) {
						sb.append(a[i][j] + " ");
					} else {
						sb.append(a[i][j]);
					}
				}
				sb.append("\n");
			}
			sb.setLength(sb.length() - 1);
			return sb.toString();
		}
		
		static String toString(double[][] a) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < a[i].length; j++) {
					if (j < a[i].length - 1) {
						sb.append(a[i][j] + " ");
					} else {
						sb.append(a[i][j]);
					}
				}
				sb.append("\n");
			}
			sb.setLength(sb.length() - 1);
			return sb.toString();
		}
		
		static String toString(String[][] a) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < a[i].length; j++) {
					if (j < a[i].length - 1) {
						sb.append(a[i][j] + " ");
					} else {
						sb.append(a[i][j]);
					}
				}
				sb.append("\n");
			}
			sb.setLength(sb.length() - 1);
			return sb.toString();
		}
		
		static int toInt(String s) throws IOException {
			return Integer.parseInt(s);
		}
		
		static long toLong(String s) throws IOException {
			return Long.parseLong(s);
		}
		
		static double toDouble(String s) throws IOException {
			return Double.parseDouble(s);
		}
		
		static int[] toIntArray(String s) throws IOException {
			String[] tokens = s.split(" ");
			int[] a = new int[tokens.length];
			for (int i = 0; i < tokens.length; i++) {
				a[i] = Integer.parseInt(tokens[i]);
			}
			return a;
		}
		
		static long[] toLongArray(String s) throws IOException {
			String[] tokens = s.split(" ");
			long[] a = new long[tokens.length];
			for (int i = 0; i < tokens.length; i++) {
				a[i] = Long.parseLong(tokens[i]);
			}
			return a;
		}
		
		static double[] toDoubleArray(String s) throws IOException {
			String[] tokens = s.split(" ");
			double[] a = new double[tokens.length];
			for (int i = 0; i < tokens.length; i++) {
				a[i] = Double.parseDouble(tokens[i]);
			}
			return a;
		}
		
		static String[] toStringArray(String s) throws IOException {
			return s.split(" ");
		}
	}
}
0