Submission #366342

#	Time	Username	Problem	Language	Result	Execution time	Memory
366342		dapig	Commuter Pass (JOI18_commuter_pass)	Java	0 / 100	2093 ms	262144 KiB

commuter_pass

//package shortpaths;

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();

	}
	
	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];
		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 (mins[pos] < next[1]) continue;
			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});
				}
			}
		}
	}
	
	void recur(int val, int par) {
		if (val == s) {
			dijk2();
			return;
		}
		for (int i : vals[val]) {
			if (i == par) continue;
			graph[i].add(new int[] {val, 0});
			graph[val].add(new int[] {i, 0});
			recur(i, val);
			graph[i].remove(graph[i].size()-1);
			graph[val].remove(graph[val].size()-1);
		}
	}
	
	void dijk2() {
		PriorityQueue<long[]> pq = new PriorityQueue<>(new SortArr());
		pq.add(new long[] {u, 0});
		long[] mins = new long[graph.length];
		Arrays.fill(mins, Long.MAX_VALUE);
		while (!pq.isEmpty()) {
			long[] next = pq.poll();
			int pos = (int) next[0];
			if (mins[pos] != Long.MAX_VALUE) continue;
			if (pos == v) {
				ans = Math.min(ans, next[1]);
				return;
			}
			if (next[1] > ans) return;
			mins[pos] = next[1];
			for (int[] i : graph[pos]) {
				long nc = mins[pos]+i[1];
				if (nc < mins[i[0]]) {
					pq.add(new long[] {i[0], nc});
				}
			}
		}
	}

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

		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();
		recur(t, -1);
		System.out.println(ans);

	}

}

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