Submission #366357

#	Time	Username	Problem	Language	Result	Execution time	Memory
366357		dapig	Commuter Pass (JOI18_commuter_pass)	Java	0 / 100	2094 ms	74260 KiB

commuter_pass

import java.io.*;
import java.util.*;

class commuter_pass {

	public static void main(String[] args) throws IOException {

		commuter_pass obj = new commuter_pass();

		obj.doStuff();

	}
	
	void gen() throws IOException {
		PrintWriter out = new PrintWriter(new File("filename.in"));
		out.println("50000 99996");
		out.println("1 50000");
		out.println("2 3");
		for (int i = 2; i <= 49999; i++) {
			out.println("1 "+i+" 1");
		}
		for (int i = 2; i <= 49999; i++) {
			out.println("50000 "+i+" 1");
		}
		out.close();
	}
	
	class SortArr implements Comparator<long[]> {

		@Override
		public int compare(long[] o1, long[] o2) {
			return (o1[1]<o2[1])?-1:((o1[1]>o2[1])?1:0);
		}
		
	}
	
	ArrayList<Integer>[] vals;
	@SuppressWarnings("unchecked")
	void dijk1() {
		PriorityQueue<long[]> pq = new PriorityQueue<>(new SortArr());
		pq.add(new long[] {s, 0});
		long[] mins = new long[graph.length];
		Arrays.fill(mins, Long.MAX_VALUE);
		vals = new ArrayList[graph.length];
		boolean[] vis = new boolean[graph.length];
		for (int i = 0; i < vals.length; i++) {
			vals[i] = new ArrayList<>();
		}
		while (!pq.isEmpty()) {
			long[] next = pq.poll();
			int pos = (int) next[0];
			if (vis[pos]) continue;
			vis[pos] = true;
			for (int[] i : graph[pos]) {
				long nc = mins[pos]+i[1];
				if (nc < mins[i[0]]) {
					mins[i[0]] = nc;
					vals[i[0]] = new ArrayList<>();
					vals[i[0]].add(pos);
					pq.add(new long[] {i[0], nc});
				} else if (nc == mins[i[0]]) {
					vals[i[0]].add(pos);
					pq.add(new long[] {i[0], nc});
				}
			}
		}
	}
	
	long[] minu, minv;
	long recur(int val, int par) {
		minv[val] = Math.min(minv[val], varr[val]);
		if (val == s) {
			minu[s] = uarr[s];
			return minu[s];
		} else {
			long thisu = uarr[val];
			for (int i : vals[val]) {
				if (i == par) continue;
				minv[i] = minv[val];
				thisu = Math.min(thisu, recur(i, val));
			}
			minu[val] = thisu;
			return thisu;
		}
	}
	
	long[] dijk2(int n) {
		PriorityQueue<long[]> pq = new PriorityQueue<>(new SortArr());
		pq.add(new long[] {n, 0});
		long[] mins = new long[graph.length];
		Arrays.fill(mins, Long.MAX_VALUE);
		boolean[] vis = new boolean[graph.length];
		mins[n] = 0;
		while (!pq.isEmpty()) {
			long[] next = pq.poll();
			int pos = (int) next[0];
			if (vis[pos]) continue;
			vis[pos] = true;
			for (int[] i : graph[pos]) {
				long nc = mins[pos]+i[1];
				if (nc < mins[i[0]]) {
					mins[i[0]] = nc;
					pq.add(new long[] {i[0], nc});
				}
			}
		}
		return mins;
	}

	int n, m, s, t, u, v;
	ArrayList<int[]>[] graph;
	long ans = Long.MAX_VALUE;
	long[] uarr, varr;
	@SuppressWarnings("unchecked")
	private void doStuff() throws IOException {

		gen();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		s = Integer.parseInt(st.nextToken())-1;
		t = Integer.parseInt(st.nextToken())-1;
		st = new StringTokenizer(br.readLine());
		u = Integer.parseInt(st.nextToken())-1;
		v = Integer.parseInt(st.nextToken())-1;
		graph = new ArrayList[n];
		for (int i = 0; i < graph.length; i++) {
			graph[i] = new ArrayList<>();
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken())-1;
			int b = Integer.parseInt(st.nextToken())-1;
			int v = Integer.parseInt(st.nextToken());
			graph[a].add(new int[] {b, v});
			graph[b].add(new int[] {a, v});
		}
		br.close();
		
		dijk1();
		uarr = dijk2(u);
		varr = dijk2(v);
		minu = new long[graph.length];
		minv = new long[graph.length];
		Arrays.fill(minu, Long.MAX_VALUE);
		Arrays.fill(minv, Long.MAX_VALUE);
		recur(t, -1);
		long ans = uarr[v];
		for (int i = 0; i < graph.length; i++) {
			if (minu[i] != Long.MAX_VALUE &&
					minv[i] != Long.MAX_VALUE) {
				ans = Math.min(ans, minu[i]+minv[i]);
			}
		}
		System.out.println(ans);

	}

}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45